QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#90678 | #6123. JAG Graph Isomorphism | qgoi_official# | WA | 4ms | 9752kb | C++14 | 2.8kb | 2023-03-24 18:00:53 | 2023-03-24 18:00:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(){
int f=1,j=0;
char w=getchar();
while(!isdigit(w)){
if(w=='-')f=-1;
w=getchar();
}
while(isdigit(w)){
j=j*10+w-'0';
w=getchar();
}
return f*j;
}
const int N=2000010;
const int moda=1000000087,modb=1000000007;
int n;
struct Work{
int head[N],fro[N*2],to[N*2],tail;
inline void adlin(int x,int y){
to[++tail]=y,fro[tail]=head[x],head[x]=tail;
return ;
}
int huan[N],cnt;
int inque[N],rt;
bool wk[N];
void dfs1(int u,int fa){
wk[u]=true;
for(int k=head[u];k;k=fro[k]){
int x=to[k];
if(x==fa)continue;
if(wk[x])inque[x]=1,inque[u]=1,rt=x;
else dfs1(x,u);
}
return ;
}
void dfs2(int u,int fa){
wk[u]=true;
for(int k=head[u];k;k=fro[k]){
int x=to[k];
if(x==fa||wk[x])continue;
else dfs2(x,u),inque[u]+=(inque[x]==2)?0:inque[x];
}
return ;
}
void dfs3(int u,int fa){
wk[u]=true;
huan[++cnt]=u;
for(int k=head[u];k;k=fro[k]){
int x=to[k];
if(!inque[x]||wk[x])continue;
dfs3(x,u);
}
return ;
}
unsigned long long f[N],pwa[N],pwb[N],pre[N],bac[N];
int siz[N];
void cal(int u,int fa){
siz[u]=1;
for(int k=head[u];k;k=fro[k]){
int x=to[k];
if(inque[x]||x==fa)continue;
cal(x,u);
siz[u]+=siz[x];
f[u]+=f[x]*pwa[siz[x]];
}
f[u]+=pwa[siz[u]];
return ;
}
void work(){
pwa[0]=pwb[0]=1;
for(int i=1;i<=n;i++)pwa[i]=pwa[i-1]*moda,pwb[i]=pwb[i-1]*modb;
for(int i=1;i<=n;i++){
int x=rd(),y=rd();
adlin(x,y),adlin(y,x);
}
dfs1(1,0);
for(int i=1;i<=n;i++)wk[i]=false;
dfs2(1,0);
// for(int i=1;i<=n;i++)cout<<inque[i]<<" ";
// cout<<"\n";
for(int i=1;i<=n;i++)wk[i]=false;
dfs3(rt,0);
for(int i=1;i<=n;i++)inque[i]=false;
for(int i=1;i<=cnt;i++)inque[huan[i]]=true;
for(int i=1;i<=cnt;i++)cal(huan[i],0);
// for(int i=1;i<=cnt;i++)cout<<huan[i]<<" ";
// cout<<"\n";
// for(int i=1;i<=cnt;i++)cout<<huan[i]<<":"<<f[huan[i]]<<"\n";
// cout<<"\n";
for(int i=1;i<=cnt;i++)pre[i]=pre[i-1]*modb+f[huan[i]];
for(int i=cnt;i>=1;i--)bac[i]=bac[i+1]+f[huan[i]]*pwb[cnt-i];
// for(int i=1;i<=cnt;i++)cout<<pre[i]<<" ";
// cout<<"\n";
// for(int i=1;i<=cnt;i++)cout<<bac[i]<<" ";
// cout<<"\n";
return ;
}
}A,B;
unordered_map<unsigned long long,bool>p;
signed main(){
n=rd();
A.work(),B.work();
bool ans=false;
if(A.cnt!=B.cnt){
printf("No\n");
return 0;
}
for(int i=0;i<=A.cnt;i++){
unsigned long long ansn=A.pre[i]+A.bac[i+1]*A.pwb[i];
// cout<<i<<":"<<ansn<<"\n";
p[ansn]=true;
}
for(int i=0;i<=B.cnt;i++){
unsigned long long ansn=B.pre[i]+B.bac[i+1]*B.pwb[i];
if(p[ansn])ans=true;
// cout<<i<<":"<<ansn<<"\n";
}
printf((ans)?"Yes\n":"No\n");
return 0;
}
/*
6
1 2
1 3
2 5
2 6
3 5
4 6
1 5
1 6
2 4
2 5
2 6
3 4
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9600kb
input:
4 1 2 2 3 2 4 3 4 1 2 1 3 1 4 3 4
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 3ms
memory: 7616kb
input:
4 1 2 2 3 3 4 1 4 1 2 1 3 1 4 3 4
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 2ms
memory: 9652kb
input:
6 1 2 1 3 2 5 2 6 3 5 4 6 1 5 1 6 2 4 2 5 2 6 3 4
output:
Yes
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 0ms
memory: 7668kb
input:
903 835 491 695 797 411 56 636 367 122 715 775 564 199 77 31 593 654 460 330 25 555 345 36 527 768 760 378 753 291 51 676 73 227 883 310 389 656 259 603 836 369 901 347 231 543 259 66 772 301 592 711 738 507 499 425 462 27 458 257 328 628 83 184 645 805 495 491 311 635 874 615 259 39 193 715 673 636...
output:
No
result:
ok answer is NO
Test #5:
score: 0
Accepted
time: 4ms
memory: 9752kb
input:
700 520 12 414 245 592 324 396 343 365 93 611 99 163 524 327 310 436 373 646 392 642 15 698 393 599 682 427 341 383 14 218 330 453 441 647 223 14 26 36 118 229 27 56 604 497 177 621 352 178 349 372 257 45 533 44 407 110 343 66 468 564 253 200 27 80 62 50 201 130 5 190 12 140 643 635 130 352 465 223 ...
output:
No
result:
ok answer is NO
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 5568kb
input:
350 40 299 79 166 204 324 281 292 63 25 326 188 279 70 64 153 145 121 93 188 283 187 339 1 11 10 330 146 124 45 295 65 208 60 131 39 328 21 181 78 276 5 121 62 81 136 248 78 51 115 87 159 346 338 251 133 306 64 298 183 161 42 14 207 5 73 259 89 269 194 334 129 118 82 50 314 246 72 180 68 166 283 249...
output:
No
result:
wrong answer expected YES, found NO