QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769296#9570. Binary TreekisakiWA 1ms3792kbC++142.2kb2024-11-21 17:00:092024-11-21 17:00:09

Judging History

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

  • [2024-11-21 17:00:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3792kb
  • [2024-11-21 17:00:09]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 100010
typedef long long ll;
int t,n,root;
int l[N],r[N],fa[N],size[N],cnt;
void dfs_size(int p){
	size[p]=1;
	if(l[p])dfs_size(l[p]),size[p]+=size[l[p]];
	if(r[p])dfs_size(r[p]),size[p]+=size[r[p]];
}
int max(int a,int b,int c){
	return std::max(a,std::max(b,c));
}
int pos;
void minn(int p,int min){
	if(fa[p]&&l[p]&&r[p]){
		if(max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]])<=min){
			min=max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]]);
			pos=p;
		}
	}
	else if(max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]])<min&&((fa[p]&&l[p])||(fa[p]&&r[p])||(l[p]&&r[p]))){
		min=max(size[l[p]],size[r[p]],size[root]-size[l[p]]-size[r[p]]);
		pos=p;
	}
	if(l[p])minn(l[p],min);
	if(r[p])minn(r[p],min);
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)size[i]=0,fa[i]=0;
		for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]),fa[l[i]]=fa[r[i]]=i;
		for(int i=1;i<=n;i++){
			if(!fa[i]){
				root=i;
				break;
			}
		}
		int st;
		dfs_size(root);
		while(size[root]>2){
			
			minn(root,INF);
			if(l[pos]&&r[pos]){//d=2 or 3
				std::cout<<"? "<<l[pos]<<" "<<r[pos]<<"\n";std::cout.flush();
				scanf("%d",&st);
				if(st==0)root=l[pos],fa[root]=0;
				else if(st==2)root=r[pos],fa[root]=0;
				else l[pos]=r[pos]=0;
			}
			else if(l[pos]){
				std::cout<<"? "<<l[pos]<<" "<<fa[pos]<<"\n";std::cout.flush();
				scanf("%d",&st);
				if(st==0)root=l[pos],fa[root]=0;
				else l[pos]=r[pos]=0;
			}
			else if(r[pos]){
				std::cout<<"? "<<r[pos]<<" "<<fa[pos]<<"\n";std::cout.flush();
				scanf("%d",&st);
				if(st==0)root=r[pos],fa[root]=0;
				else l[pos]=r[pos]=0;
			}dfs_size(root);
		}
		if(size[root]==1){
			std::cout<<"! "<<root<<"\n";std::cout.flush();
		}
		else{
			int qwq=std::max(l[root],r[root]);
			std::cout<<"? "<<qwq<<" "<<root<<"\n";std::cout.flush();
			scanf("%d",&st);
			if(st==0){
				std::cout<<"! "<<qwq<<"\n";std::cout.flush();
			}
			else{
				std::cout<<"! "<<root<<"\n";std::cout.flush();
			}
		}
	}
 	return 0;
}
/*
1
7
2 0
3 0
4 0
5 0
6 0
7 0
0 0


*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3648kb

input:

2
5
0 0
1 5
2 4
0 0
0 0
1
1
2
0 2
0 0
2

output:

? 1 5
? 2 4
! 3
? 2 1
! 1

result:

ok OK (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3792kb

input:

5555
8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4
0
2
0
8
0 0
1 4
2 0
0 0
7 8
0 0
3 0
6 0
0
1
2
8
5 8
0 0
1 7
0 0
0 0
4 2
0 0
6 0
2
1
0
5
4 5
3 1
0 0
0 0
0 0
1
1
8
0 0
0 0
5 6
0 0
1 4
2 0
3 8
0 0
0
0
5
3 0
5 1
0 0
0 0
4 0
2
0
5
5 0
0 0
0 0
3 0
2 4
1
2
3
3 0
1 0
0 0
1

output:

? 8 6
? 5 4
? 3 4
! 3
? 3 5
? 1 4
? 2 3
! 3
? 5 8
? 4 2
? 6 8
! 6
? 4 5
? 3 1
! 2
? 5 6
? 1 4
! 1
? 5 1
? 3 1
! 3
? 2 4
? 5 1
! 1
? 3 2
? 1 2

result:

wrong answer Too many queries (test case 8)