Hello to Everybody!
Can anybody help me, say any hints, how to solve this problem?
Thank You!
10729 - Treequivalence
Moderator: Board moderators
-
- New poster
- Posts: 26
- Joined: Mon Nov 13, 2006 3:53 am
same label, be careful!!
Hey, a tree could consist of same labels.
I used OLE to test and found that. Be carful.
I used OLE to test and found that. Be carful.
Re: 10729 - Treequivalence
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10729 - Treequivalence
Input:AC output:Note that order must be preserved.
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
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
Check input and AC output for thousands of problems on uDebug!