QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#745732	#9570. Binary Tree	zq500	AC ✓	257ms	17796kb	C++14	3.2kb	2024-11-14 11:17:16	2024-11-14 11:17:17

Judging History

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

[2024-11-14 11:17:17]
评测

测评结果：AC
用时：257ms
内存：17796kb

查看

[2024-11-14 11:17:16]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+20;
int n,rt;
int fa[maxn],sz[maxn];
vector<int>v[maxn];
int dfs(int x)
{
	sz[x]=1;
	int mx=0;
	for(int y:v[x])
	{
		dfs(y);
		sz[x]+=sz[y];
		mx=max(mx,sz[y]);
	}
	mx=max(mx,n-sz[x]);
	if(n>=mx*2)rt=x;
	return sz[x];
}
void solve()
{
	
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		v[i].clear();
		fa[i]=0;
	}
	for(int i=1,x,y;i<=n;i++)
	{
		cin>>x>>y;
		if(x)
		{
			fa[x]=i;
			v[i].push_back(x);
		}
		if(y)
		{
			fa[y]=i;
			v[i].push_back(y);
		}
	}
	if(n==1)
	{
		cout<<"! "<<1<<"\n";
		cout.flush();
		return;
	}
	int root=0;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==0)root=i;
	}
//	cout<<(int)(log2(n))<<"\n";
	for(int p=(int)(log2(n)),op;p>=1;p--)
	{
		for(int i=1;i<=n;i++)
		{
			sz[i]=0;
		}
		dfs(root);
		if(v[rt].size()==2)
		{
			if(fa[rt])
			{
				if(n-sz[rt]>=sz[v[rt][0]] && n-sz[rt]>=sz[v[rt][1]])
				{
					if(sz[v[rt][0]]<sz[v[rt][1]])swap(v[rt][0],v[rt][1]);
					
					cout<<"? "<<v[rt][0]<<" "<<fa[rt]<<"\n";
					cout.flush();
					cin>>op;
					if(op==0)
					{
						root=v[rt][0];
						fa[root]=0;
						n-=n-sz[root];
					}else if(op==1)
					{
						root=rt;
						fa[root]=0;
						n-=n-sz[rt]+sz[v[rt][0]];
						v[rt].erase(v[rt].begin());
					}else if(op==2)
					{
						n-=sz[rt];
						if(rt==v[fa[rt]][0])v[fa[rt]].erase(v[fa[rt]].begin());
						else v[fa[rt]].erase(v[fa[rt]].begin()+1);
					}
				}else
				{
					cout<<"? "<<v[rt][0]<<" "<<v[rt][1]<<"\n";
					cout.flush();
					cin>>op;
					if(op==0)
					{
						root=v[rt][0];
						fa[root]=0;
						n-=n-sz[root];
					}else if(op==1)
					{
						n-=sz[rt]-1;
						v[rt].clear();
					}else if(op==2)
					{
						root=v[rt][1];
						fa[root]=0;
						n-=n-sz[root];
					}
				}
			}else
			{
				cout<<"? "<<v[rt][0]<<" "<<v[rt][1]<<"\n";
				cout.flush();
				cin>>op;
				if(op==0)
				{
					root=v[rt][0];
					fa[root]=0;
					n-=n-sz[root];
				}else if(op==1)
				{
					n-=sz[rt]-1;
					v[rt].clear();
				}else if(op==2)
				{
					root=v[rt][1];
					fa[root]=0;
					n-=n-sz[root];
				}
			}
		}else if(v[rt].size()==1)
		{
			if(fa[rt])
			{
				cout<<"? "<<v[rt][0]<<" "<<fa[rt]<<"\n";
				cout.flush();
				cin>>op;
				if(op==0)
				{
					root=v[rt][0];
					fa[root]=0;
					n-=n-sz[root];
				}else if(op==1)
				{
					root=rt;
					n=1;
					fa[root]=0;
					v[root].clear();
					
				}else if(op==2)
				{
					n-=sz[rt];
					if(rt==v[fa[rt]][0])v[fa[rt]].erase(v[fa[rt]].begin());
					else v[fa[rt]].erase(v[fa[rt]].begin()+1);
				}
			}else
			{
				cout<<"? "<<v[rt][0]<<" "<<rt<<"\n";
				cout.flush();
				cin>>op;
				if(op==0)
				{
					root=v[rt][0];
					fa[root]=0;
					n-=n-sz[root];
				}else if(op==2)
				{
					n-=sz[rt]-1;
					v[rt].clear();
				}
			}
		}
//		cout<<root<<" "<<rt<<" "<<n<<"\n";
//		cout.flush();
	}
	for(int i=1;i<=n;i++)
	{
		sz[i]=0;
	}
	dfs(root);
	cout<<"! "<<rt<<"\n";
	cout.flush();
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 6028kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: 0

Accepted

time: 39ms

memory: 6864kb

input:

output:

result:

ok OK (5555 test cases)

Test #3:

score: 0

Accepted

time: 22ms

memory: 6056kb

input:

output:

result:

ok OK (600 test cases)

Test #4:

score: 0

Accepted

time: 95ms

memory: 17796kb

input:

output:

? 43991 70790
? 46637 98261
? 69452 58487
? 39509 59517
? 57474 54741
? 657 74598
? 9151 6159
? 35868 36942
? 528 36409
? 66747 37416
? 27728 95772
? 70205 7642
? 20147 11958
? 59682 22076
? 83246 16046
? 54741 83246
! 83246
? 5676 85780
? 39704 57748
? 58489 42043
? 30188 50842
? 36012 24131
? 1857...

result:

ok OK (2 test cases)

Test #5:

score: 0

Accepted

time: 47ms

memory: 13728kb

input:

output:

result:

ok OK (15 test cases)

Test #6:

score: 0

Accepted

time: 44ms

memory: 13776kb

input:

output:

? 2 1
! 1
? 1 2
? 4 1
! 4
? 8 3
? 5 8
? 2 5
! 5
? 3 4
? 13 2
? 16 13
? 9 16
! 9
? 12 30
? 11 6
? 1 18
? 32 1
? 2 32
! 32
? 60 3
? 15 63
? 52 12
? 43 58
? 47 43
? 2 47
! 2
? 80 113
? 16 115
? 63 112
? 25 50
? 81 89
? 11 81
? 114 11
! 114
? 90 113
? 248 20
? 8 130
? 58 142
? 239 182
? 192 161
? 244 19...

result:

ok OK (16 test cases)

Test #7:

score: 0

Accepted

time: 50ms

memory: 13612kb

input:

output:

result:

ok OK (15 test cases)

Test #8:

score: 0

Accepted

time: 30ms

memory: 6184kb

input:

output:

result:

ok OK (600 test cases)

Test #9:

score: 0

Accepted

time: 57ms

memory: 9088kb

input:

2
99999
0 0
7999 97267
75750 37659
0 0
0 0
33761 92098
90707 18838
13602 27569
0 0
0 0
0 0
0 0
0 0
0 0
0 0
14586 86647
1519 23132
0 0
3430 14643
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
47066 36968
95308 38482
34100 25297
0 0
0 0
0 0
0 0
88902 58991
0 0
0 0
66315 68538
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0...

output:

? 69076 50379
? 11838 79924
? 18079 15463
? 72017 29994
? 80147 27856
? 80763 26264
? 39876 84186
? 73287 34615
? 43462 43070
? 38721 85806
? 84940 93114
? 3443 79116
? 49016 68555
? 56289 87545
? 32426 3887
! 3887
? 78976 72481
? 84675 96633
? 2124 81852
? 13836 79494
? 80643 24965
? 38932 5573
? 5...

result:

ok OK (2 test cases)

Test #10:

score: 0

Accepted

time: 32ms

memory: 8052kb

input:

output:

result:

ok OK (15 test cases)

Test #11:

score: 0

Accepted

time: 33ms

memory: 8040kb

input:

output:

result:

ok OK (16 test cases)

Test #12:

score: 0

Accepted

time: 36ms

memory: 7964kb

input:

output:

result:

ok OK (15 test cases)

Test #13:

score: 0

Accepted

time: 25ms

memory: 6076kb

input:

output:

result:

ok OK (600 test cases)

Test #14:

score: 0

Accepted

time: 62ms

memory: 13136kb

input:

2
99999
96748 53986
34197 77552
29863 63559
79099 26449
45078 1051
0 0
27416 4135
0 0
38606 81189
93892 68603
48776 185
79602 18311
51243 83678
89044 40032
28883 35663
0 0
0 0
21603 15821
0 0
51448 75971
70275 8326
0 0
0 0
57049 72937
3297 94939
0 0
59258 39159
3205 34675
54876 24769
0 0
0 0
0 0
851...

output:

? 27459 71188
? 24680 87538
? 11855 13278
? 64417 35922
? 56721 58885
? 77695 12579
? 87441 91627
? 30394 63243
? 80843 10437
? 7898 61091
? 71930 23154
? 44598 18254
? 84575 11590
? 11182 46612
? 91627 46612
? 1195 91627
! 91627
? 4235 50499
? 11190 42167
? 20945 96466
? 35201 37783
? 48920 28303
?...

result:

ok OK (2 test cases)

Test #15:

score: 0

Accepted

time: 41ms

memory: 10404kb

input:

output:

? 1 3
! 2
? 6 2
? 1 7
! 7
? 6 15
? 10 4
? 5 8
! 5
? 12 14
? 8 10
? 27 18
? 2 16
! 16
? 15 38
? 47 22
? 13 27
? 29 44
? 4 32
! 44
? 34 51
? 33 108
? 124 30
? 9 27
? 87 126
? 73 2
! 2
? 83 124
? 22 162
? 230 84
? 112 110
? 51 147
? 29 223
? 117 212
! 117
? 460 322
? 386 146
? 81 102
? 473 135
? 263 27...

result:

ok OK (15 test cases)

Test #16:

score: 0

Accepted

time: 39ms

memory: 10700kb

input:

output:

result:

ok OK (16 test cases)

Test #17:

score: 0

Accepted

time: 35ms

memory: 10372kb

input:

output:

result:

ok OK (15 test cases)

Test #18:

score: 0

Accepted

time: 62ms

memory: 9412kb

input:

2
99999
0 0
88119 0
72740 0
6901 19702
0 0
10620 84889
0 0
9552 63972
45156 60768
9152 72379
0 0
59875 97207
48193 0
17282 54916
65927 27713
80083 15817
36966 75381
0 0
77279 56298
0 0
11554 61779
0 0
89976 0
65282 42151
95206 62876
97329 86772
0 0
0 0
0 0
11820 0
0 0
20432 0
50520 39907
0 0
46948 1...

output:

? 35226 52174
? 16093 26122
? 11494 10853
? 91694 11494
? 73088 90037
? 21572 90037
? 51091 99968
? 93596 7067
? 75096 73345
? 61908 88342
? 54898 20607
? 79113 54898
? 28780 82981
? 86442 82981
! 82981
? 91773 80592
? 68004 50906
? 65219 73367
? 33796 20489
? 61722 74041
? 56446 35779
? 85560 35779...

result:

ok OK (2 test cases)

Test #19:

score: 0

Accepted

time: 257ms

memory: 6028kb

input:

output:

? 1 2
! 2
? 1 2
! 1
? 1 2
! 2
? 1 2
! 1
? 1 2
! 2
? 1 2
! 1
? 1 2
! 1
? 1 2
! 1
? 1 2
! 1
? 1 2
! 2
? 1 2
! 1
? 1 2
! 1
? 1 2
! 2
? 1 2
! 2
? 1 2
! 1
? 1 2
! 2
? 1 2
! 2
? 1 2
! 2
? 1 2
! 2
? 1 2
! 1
? 1 2
! 1
? 1 2
! 1
? 1 2
! 2
? 1 2
! 1
? 1 2
! 1
? 1 2
! 2
? 1 2
! 2
? 1 2
! 2
? 1 2
! 2
? 1 2
! 2
...

result:

ok OK (100000 test cases)

Extra Test:

score: 0

Extra Test Passed