10729 - Treequivalence

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

10729 - Treequivalence

Post by Victor Barinov » Thu Oct 07, 2004 8:41 pm

Hello to Everybody!

Can anybody help me, say any hints, how to solve this problem?

Thank You!

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

same label, be careful!!

Post by TimeString » Tue Mar 27, 2007 6:00 am

Hey, a tree could consist of same labels.
I used OLE to test and found that. Be carful.

Farsan
New poster
Posts: 34
Joined: Fri Aug 12, 2011 6:37 am

Re: 10729 - Treequivalence

Post by Farsan » Sat May 31, 2014 4:59 pm

Can anyone help please?getting WA...

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
int Set(int N,int pos){return N=N | (1<<pos);}
int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos){return (bool)(N & (1<<pos));}
int cnt_leading_zero_bits(int N){return __builtin_clz(N);}
int cnt_trailing_zero_bits(int N){return __builtin_ctz(N);}
int cnt_no_of_bits_on(int N){return __builtin_popcount(N);}

//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const


using namespace std;



int main()
{
    int i,j,k,m,n,t;
    cin>>t;
    getchar();
    while(t--)
    {
        vector<int>v[205],v2[205];
        string s1,s2;
        getline(cin,s1);
        getline(cin,s2);
        map<char,int>mp;
        int cnt=0;
        stack<char>s;
        char ch;
        for(i=0,j=s1.size();i<j;i++)
        {
            if(s1[i]==',')
            {
                continue;
            }
            if(s1[i]!=')')
            {
                if(s1[i]!='(')
                {
                    if(!mp[s1[i]])
                    mp[s1[i]]=++cnt;
                }
                s.push(s1[i]);
            }
            else
            {
                queue<char>q;
                while(s.top()!='(')
                {
                    ch=s.top();
                    s.pop();
                    q.push(ch);
                }
                s.pop();
                ch=s.top();
                k=mp[ch];
                while(!q.empty())
                {
                    ch=q.front();
                    q.pop();
                    m=mp[ch];
                    v[k].push_back(m);
                    v[m].push_back(k);
                }
            }
        }
        for(i=0,j=s2.size();i<j;i++)
        {
            if(s2[i]==',')
            {
                continue;
            }
            if(s2[i]!=')')
            {
                if(s2[i]!='(')
                {
                    if(!mp[s2[i]])
                    mp[s2[i]]=++cnt;
                }
                s.push(s2[i]);
            }
            else
            {
                queue<char>q;
                while(s.top()!='(')
                {
                    ch=s.top();
                    s.pop();
                    q.push(ch);
                }
                s.pop();
                ch=s.top();
                k=mp[ch];
                while(!q.empty())
                {
                    ch=q.front();
                    q.pop();
                    m=mp[ch];
                    v2[k].push_back(m);
                    v2[m].push_back(k);
                }
            }
        }
        bool ok=true;
        for(i=1;i<=cnt&&ok;i++)
        {
            sort(v[i].begin(),v[i].end());
            sort(v2[i].begin(),v2[i].end());
            j=v[i].size();
            k=v2[i].size();
            if(j!=k)
            ok=false;
            j=0;
            while(j<k&&ok)
            {
                if(v[i][j]!=v2[i][j])
                ok=false;
                j++;
            }
        }
        if(ok)
        cout<<"same\n";
        else
        cout<<"different\n";
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10729 - Treequivalence

Post by brianfry713 » Fri Jun 13, 2014 11:00 pm

Input:

Code: Select all

100
T(T(Y(T),M(R)),P,J,C(H))
R(M(T(T(P,J,C(H)),Y(T))))
T(B)
B(T)
U(P(K),F)
P(U(F),K)
I(S(B(Q(W,A),N(M),H)),H)
S(B(Q(W,A),N(M),H),I(H))
F(L(V),G(Q))
L(F(G(Q)),V)
J(E(M))
M(E(J))
U(A(K,B,Z,I))
U(A(K,B,Z,I))
A(W(S,T),X)
A(W(S,T),X)
S(Y(Y(O),U(N(S,E,R(D)))))
D(R(N(U(Y(Y(O),S)),S,E)))
U
U
Y(F(A(Q(X,W),L(U)),V))
X(Q(A(L(U),F(V,Y)),W))
C(L(Z),V)
V(C(L(Z)))
G(B(D(L(Y(Z))),J,X,T,V))
B(D(L(Y(Z))),J,X,G,T,V)
O
O
Y(Y(D(P(M(C),V,P),L)))
Y(D(P(M(C),V,P),L),Y)
Z(Y(U,Y,B),R)
U(Y(Y,Z(R),B))
K(B(Q(L),V,K,F),Y(A))
B(K(Y(A)),Q(L),V,K,F)
E(Q(P(U(J),F),W),P)
P(E(Q(P(U(J),F),W)))
C(G(Y(R(I))))
I(R(Y(G(C))))
I(K(F(P)))
F(K(I),P)
X
X
U(M(Y(J,V),O,Y))
V(Y(M(U,O,Y),J))
P(C(C(H)),O(E))
P(C(C(H)),O(E))
X(T(L(Q)),Q(T(C)))
C(T(Q(X(T(L(Q))))))
J(E(T,X(V),I),N(Z,W(Y)))
Y(W(N(J(E(T,X(V),I)),Z)))
D
D
J(R,N(I(G)))
I(N(J(R)),G)
C(N(Y(E(E)),E,I))
C(N(Y(E(E)),E,I))
Y(X(H(C,G(W)),M,G(R)))
R(G(X(H(C,G(W)),M,Y)))
M(Q(T))
T(Q(M))
W(E(T))
W(E(T))
O(C)
C(O)
K(L,D)
K(L,D)
T(Q(V(J(R,E))))
V(J(R,E),Q(T))
Q(F,K(V(G)),T,U,K)
U(Q(F,K(V(G)),T,K))
P(Z)
P(Z)
A(V)
A(V)
C(I,T(U))
U(T(C(I)))
F(V(V(U(K,C),N(K,T)),C))
K(U(V(V(F,C),N(K,T)),C))
T(M(R(P(C,L,S),D)))
T(M(R(P(C,L,S),D)))
O(E)
O(E)
J(P(O(B,G)))
G(O(P(J),B))
F(J(I(X),A),Y,Z(I))
X(I(J(F(Y,Z(I)),A)))
Q(Q)
Q(Q)
W(O(V(S(E(V(L(S(U(Q)))))))))
Q(U(S(L(V(E(S(V(O(W)))))))))
C(F)
F(C)
J(W(R,C))
C(W(R,J))
Q(U,J,Z)
U(Q(J,Z))
B(T(C(P(U),W),D(A),Y))
P(C(W,T(D(A),Y,B)),U)
O(W,R(A))
O(W,R(A))
Y(J(A(C,O(Y)),K))
Y(J(A(C,O(Y)),K))
S(S(F))
S(S,F)
B(W(O,W))
O(W(W,B))
M(E(A,Y(I(F(T,K))),O))
I(Y(E(A,M,O)),F(T,K))
S(E(D))
E(S,D)
P(U(D,D(F(A(E))),I))
E(A(F(D(U(D,P,I)))))
X(P(U))
U(P(X))
K(D(I,D,K))
D(D(I,K,K))
F(C(H,B(C),N))
B(C(H,N,F),C)
R(P(L(Y(A(T),K),D)))
T(A(Y(L(P(R),D),K)))
A(M(G(Z),I))
G(M(A,I),Z)
O(T(B))
O(T(B))
A(Y(V),D)
Y(A(D),V)
M(V(W(F(C)),W(N)))
M(V(W(F(C)),W(N)))
K(T(V,J))
V(T(K,J))
F(D(W,V))
D(W,V,F)
A
A
O(K(C(X(J(C)),E(S(V)))),Y)
C(J(X(C(E(S(V)),K(O(Y))))))
Z(M(D(F(B,D),K),M(T)),E)
F(D(M(M(T),Z(E)),K),B,D)
K(S(W(X,J)),U(T,B))
J(W(S(K(U(T,B))),X))
R
R
S(F(Y(S,M,B,R)))
M(Y(F(S),S,B,R))
F(D(W(K(X(D),B)),L))
D(W(K(X(D),B)),L,F)
C(B(X(U(V))))
B(C,X(U(V)))
K
K
X(T(P(Q)))
P(T(X),Q)
U
U
W(S(Z(M),I(S,C)))
S(I(S(W,Z(M)),C))
W(T,R)
T(W(R))
Z(E,J)
Z(E,J)
B(C(Q(B(C(D),W(O)))))
W(B(C(D),Q(C(B))),O)
J(X(N(H,N),B))
J(X(N(H,N),B))
K(M(D,W(J(M(Y)),R),B,D))
D(M(W(J(M(Y)),R),K,B,D))
I(E)
E(I)
Q(M(C(R)))
M(Q,C(R))
W(O)
O(W)
K(I(O),F(T(L),J,O))
I(K(F(T(L),J,O)),O)
M(Q(K(G)),T)
M(Q(K(G)),T)
G(S(K(N(C(O))),D))
C(N(K(S(G,D))),O)
S(H(Q(I(A(T(J)),B,V))))
S(H(Q(I(A(T(J)),B,V))))
U(Q(P,H),T)
P(Q(H,U(T)))
V(J(W(Y(W)),E,R),H(Y))
J(V(H(Y)),W(Y(W)),E,R)
P(X(J),Q,N(H))
J(X(P(Q,N(H))))
J(N(Q(G(O),R(O),U)),Q,Y)
O(R(Q(G(O),N(J(Q,Y)),U)))
U(H(R))
H(R,U)
V(S)
V(S)
R(B(R,U))
B(R,R,U)
R(G(V(Z(W(Y(J))))))
R(G(V(Z(W(Y(J))))))
X(X,Q,G(R),X(X))
X(X,Q,G(R),X(X))
H
H
AC output:

Code: Select all

same
same
same
same
same
same
same
same
different
same
different
same
different
same
same
different
same
same
same
same
same
different
same
same
same
same
same
same
different
same
same
same
same
same
different
same
same
same
different
same
same
same
different
same
same
same
different
same
same
same
same
same
same
different
same
different
same
different
different
different
different
same
same
same
different
same
same
same
different
same
same
different
same
same
same
same
same
different
same
same
different
same
different
same
same
same
same
same
different
same
same
same
same
different
same
same
same
same
same
same
Note that order must be preserved.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 107 (10700-10799)”