10729 - Treequivalence

[Victor Barinov]

Hello to Everybody!

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

Thank You!

[TimeString]

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

[Farsan]

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]

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.