QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#90678#6123. JAG Graph Isomorphismqgoi_official#WA 4ms9752kbC++142.8kb2023-03-24 18:00:532023-03-24 18:00:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-24 18:00:55]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9752kb
  • [2023-03-24 18:00:53]
  • 提交

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