QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#559372#8220. 众生之门Idtwtei0 0ms6544kbC++202.2kb2024-09-11 21:43:572024-09-11 21:44:03

Judging History

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

  • [2024-09-11 21:44:03]
  • 评测
  • 测评结果：0
  • 用时：0ms
  • 内存：6544kb
查看
  • [2024-09-11 21:43:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
const int N=5e4+100,B=16;
mt19937 rnd(time(0));
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,s,t,id[N];
vector<int> G[N];

int dep[N],dfn[N],d_c=0,st[N][B+5];
inline int get(int x,int y){ return dfn[x]<dfn[y]?x:y; }
void dfs0(int u,int fu){
	st[dfn[u]=++d_c][0]=fu,dep[u]=dep[fu]+1;
	for(int v:G[u]) if(v!=fu) dfs0(v,u);
}
inline void init(){ for(int k=1;k<=B;++k) for(int i=1;i+(1<<k)-1<=n;++i) st[i][k]=get(st[i][k-1],st[i+(1<<(k-1))][k-1]); }
inline int flca(int x,int y){ if(x==y) return x; if((x=dfn[x])>(y=dfn[y])) swap(x,y); int k=__lg(y-(++x)+1); return get(st[x][k],st[y+1-(1<<k)][k]); }
inline int fdis(int x,int y){ return dep[x]+dep[y]-2*dep[flca(x,y)]; }

void solve(){
	
	n=rd,s=rd,t=rd;
	for(int i=1,x,y;i<n;++i) x=rd,y=rd,G[x].pb(y),G[y].pb(x);
	
	dfs0(1,0),init();
	
	for(int i=1;i<=n;++i) id[i]=i;
	shuffle(id+1,id+n+1,rnd);
	
	for(int i=2;i<=n;++i) if(id[i]==s) swap(id[1],id[i]);
	for(int i=1;i<n;++i) if(id[i]==t) swap(id[n],id[i]);
	
	int cur=0; for(int i=1;i<n;++i) cur^=fdis(id[i],id[i+1]);
	
	for(int i=1;cur>1&&i<=200*n;++i){
		int x=rnd()%n+1,y=rnd()%n+1;
		while(x==1||x==n) x=rnd()%n+1;
		while(y==1||y==n||x==y) y=rnd()%n+1; 
		cur^=fdis(id[x],id[x-1])^fdis(id[y],id[x-1]);
		cur^=fdis(id[x],id[x+1])^fdis(id[y],id[x+1]);
		cur^=fdis(id[y],id[y-1])^fdis(id[x],id[y-1]);
		cur^=fdis(id[y],id[y+1])^fdis(id[x],id[y+1]);
		swap(id[x],id[y]);
	}
	if(cur>1){
		for(int i=1;cur>3&&i<=200*n;++i){
			int x=rnd()%n+1,y=rnd()%n+1;
			while(x==1||x==n) x=rnd()%n+1;
			while(y==1||y==n||x==y) y=rnd()%n+1; 
			cur^=fdis(id[x],id[x-1])^fdis(id[y],id[x-1]);
			cur^=fdis(id[x],id[x+1])^fdis(id[y],id[x+1]);
			cur^=fdis(id[y],id[y-1])^fdis(id[x],id[y-1]);
			cur^=fdis(id[y],id[y+1])^fdis(id[x],id[y+1]);
			swap(id[x],id[y]);
		}		
	}
	for(int i=1;i<=n;++i) printf("%d ", id[i]); puts("");
	
	for(int i=1;i<=n;++i) G[i]={},dfn[i]=0;
	
}

int main(){
	
	int T=rd;
	while(T--) solve();
	
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

114
6 5 6
2 6
1 6
4 5
3 1
6 4
6 3 6
2 4
4 1
6 4
1 5
5 3
6 6 1
5 2
1 2
4 6
2 4
3 2
6 6 1
3 6
5 3
1 6
4 2
2 5
6 3 1
5 3
2 4
1 5
4 3
6 3
4 3 4
2 3
1 4
4 3
6 3 1
2 3
6 3
4 3
1 6
5 1
5 3 2
1 2
4 2
2 3
5 2
6 1 4
2 1
5 2
4 1
6 2
3 6
6 5 1
4 2
6 5
1 3
2 6
3 2
4 4 1
2 4
3 4
1 4
6 2 5
3 5
4 6
1 4
6 2
5 4
6 1 ...

output:

result:

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

input:

14190
43 27 2
42 3
30 36
11 24
21 22
13 8
22 30
31 29
35 1
10 6
2 23
28 17
2 26
7 37
5 19
38 43
33 39
4 28
33 7
25 31
15 1
32 18
34 27
35 12
19 32
20 17
37 42
26 34
39 10
12 27
24 43
18 6
16 9
38 9
14 15
14 41
25 3
40 13
16 8
36 41
20 5
21 40
11 29
41 24 38
21 6
20 14
26 1
6 7
17 16
39 36
8 18
36 11...

output:

27 30 7 5 29 14 24 1 26 15 37 40 42 41 16 39 4 12 22 9 10 17 36 11 28 35 23 38 20 6 25 13 33 32 31 34 43 19 3 8 18 21 2 
24 32 2 20 41 26 7 14 15 5 35 1 9 40 25 11 18 21 13 22 12 36 34 33 10 30 29 28 16 19 23 17 27 37 31 4 8 3 6 39 38 
5 8 19 26 10 20 14 16 13 6 2 18 7 17 25 15 1 4 9 21 12 23 3 27 2...

result:

Subtask #4:

score: 0
Time Limit Exceeded

Test #18:

score: 0
Time Limit Exceeded

input:

32752
15 3 4
14 12
4 12
1 10
9 13
7 6
12 5
1 12
9 15
7 9
8 12
2 6
11 6
9 3
6 10
13 12 2
10 11
10 5
1 4
12 11
4 6
2 13
6 5
9 6
8 13
6 3
4 8
13 7
15 3 6
15 10
4 2
8 5
10 3
1 3
15 2
8 4
12 9
7 8
11 8
6 13
8 12
14 8
6 12
15 5 7
8 14
10 13
11 13
13 5
2 14
15 8
15 1
6 2
7 15
9 13
15 3
6 13
15 4
12 5
15 10...

output:

3 5 14 10 12 8 15 1 2 7 11 9 13 6 4 
12 10 1 13 4 6 8 9 7 3 11 5 2 
3 13 15 8 11 4 1 2 9 10 5 14 12 7 6 
5 3 12 4 1 2 8 15 14 9 13 10 11 6 7 
10 2 3 13 5 6 11 1 15 12 14 9 7 4 8 
11 7 2 4 10 6 8 9 5 1 3 
11 1 10 6 15 7 4 5 14 3 12 2 8 13 9 
14 7 13 5 10 8 11 9 1 4 3 6 2 12 
5 1 6 4 2 9 11 8 10 7 3 
...

result:

Subtask #5:

score: 0
Time Limit Exceeded

Test #25:

score: 0
Time Limit Exceeded

input:

36059
13 9 4
5 9
10 3
3 1
13 5
12 5
7 4
2 8
8 10
4 9
11 7
6 11
1 4
13 12 6
4 12
13 9
11 2
6 12
9 12
8 5
7 6
5 3
3 7
10 8
1 5
2 10
13 10 8
3 1
5 9
4 8
6 11
7 13
13 5
1 10
12 13
9 4
11 9
2 11
8 10
12 1 4
9 2
2 12
3 2
12 11
8 2
7 4
5 1
4 1
11 7
10 9
6 9
13 10 12
7 5
11 9
12 10
9 8
3 10
8 5
4 13
13 7
6 ...

output:

9 11 13 6 8 7 10 3 12 5 1 2 4 
12 4 1 9 2 3 8 13 11 5 10 7 6 
10 13 7 5 6 4 1 2 9 3 11 12 8 
1 11 10 5 2 8 7 9 6 12 3 4 
10 4 8 11 6 2 5 7 9 1 3 13 12 
6 2 11 4 12 9 5 1 3 13 7 10 8 
1 9 10 13 6 2 3 7 12 4 5 11 8 
7 2 9 6 10 1 5 4 8 3 
11 9 12 7 4 5 6 10 3 8 2 13 1 
4 8 7 1 11 9 13 5 12 2 3 10 6 
6 ...

result:

Subtask #6:

score: 0
Wrong Answer

Test #34:

score: 0
Wrong Answer
time: 0ms
memory: 6544kb

input:

10
1000 165 244
175 661
738 362
280 462
776 922
231 578
963 615
639 836
32 418
519 220
565 733
239 951
768 847
196 200
246 119
591 288
994 586
313 46
971 515
512 811
228 908
627 339
33 337
447 488
616 319
399 727
921 615
421 509
167 354
905 382
20 356
875 414
619 904
824 940
435 244
953 663
719 962
...

output:

165 368 32 272 961 387 132 150 67 341 834 877 123 847 767 891 712 627 491 314 823 903 469 543 449 704 479 812 964 43 857 419 809 156 443 701 925 973 352 451 705 588 73 596 607 519 599 646 268 220 991 313 458 483 257 648 93 273 207 133 887 706 501 131 726 572 515 98 784 848 157 900 357 51 828 40 299 ...

result:

wrong answer Your solution is worse than Jury's in test case 2. Yours:115 Jury's:1

Subtask #7:

score: 0
Skipped

Dependency #2:

0%
English 繁體中文 简体中文

Server Time: 2024-12-05 08:45:46 | OpenSource Project