QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#749111	#9570. Binary Tree	ucup-team3294^#	RE	1ms	3604kb	C++23	2.6kb	2024-11-14 22:41:52	2024-11-14 22:41:53

Judging History

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

[2024-11-14 22:41:53]
评测

测评结果：RE
用时：1ms
内存：3604kb

查看

[2024-11-14 22:41:52]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
#define PII pair<int,int>
void solve()
{
	int n;
	cin>>n;
	vector<int> G[n+10],G1[n+10];
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		if(l) G[i].push_back(l),G[l].push_back(i);
		if(r) G[i].push_back(r),G[r].push_back(i);
	}
	int GG=0;
	auto ask=[&](int u,int v)->int{
		GG++;
		if((1LL<<GG)>n){
			return -1;
		}
		cout<<"? "<<u<<" "<<v<<endl;
		int x;
		cin>>x;
		return x;
	};
	auto print=[&](int x){
		cout<<"! "<<x<<endl;
		return;
	};
	int root=1;
	int zx,zt,m=n,k;
	vector<int> siz(n+1);
	function<void(int,int)> dfs=[&](int u,int fa){
		siz[u]=1;
		int Max=0;
		for(auto v:G[u]){
			if(v==fa) continue;
			dfs(v,u);
			siz[u]+=siz[v];
			Max=max(Max,siz[v]);
		}
		Max=max(Max,m-siz[u]);
		if(Max<zt){
			zt=Max;
			zx=u;
		}
	};
	auto find=[&](){
		zx=zt=1e18;
		dfs(root,0);
		root=zx;
	};
	function<void(int,int)> dfs1=[&](int u,int fa){
		k++;
		for(auto v:G[u]){
			if(v==fa) continue;
			G1[u].push_back(v);
			G1[v].push_back(u);
			dfs1(v,u);
		}
	};
	auto Get=[&](int x,int y){
		k=0;
		for(int i=1;i<=n;i++) G1[i].clear();
		dfs1(x,y);
		m=k;
		for(int i=1;i<=n;i++) G[i].clear();
		for(int i=1;i<=n;i++) G[i]=G1[i];
//		for(int i=1;i<=n;i++){
//			for(auto x:G[i]){
//				cout<<i<<" "<<x<<endl;
//			}
//		}
	};
	int pp=0;
	while(1){
		find();
//		cout<<root<<"11111111"<<endl;
//	    pp++;
//		if(pp==3) break;
		if(G[root].size()==0){
			print(root);
			return;
		}else if(G[root].size()==1){
			int x=ask(root,G[root][0]);
			if(x==0){
				print(root);
				return;
			}else{
				print(G[root][0]);
				return;
			}
		}else if(G[root].size()==2){
			int x=ask(G[root][0],G[root][1]);
			if(x==1){
				print(root);
				return;
			}else if(x==0){//G[root][0]
				int p=G[root][0];
				Get(G[root][0],root);
				root=p;
			}else{//G[root][1]
				int p=G[root][1];
				Get(G[root][1],root);
				root=p;
			}
		}else if(G[root].size()==3){
			int x=ask(G[root][0],G[root][1]);
			if(x==1){//G[root][2]
				int p1=root,p2=G[root][2];
				Get(G[root][2],root);
				G[p1].push_back(p2);
				G[p2].push_back(p1);m++;
			}else if(x==0){//G[root][0]
				int p=G[root][0];
				Get(G[root][0],root);
				root=p;
			}else{//G[root][1]
				int p=G[root][1];
				Get(G[root][1],root);
				root=p;
			}
		}
	}
}
/*
1
12
0 0
1 5
2 4
0 11
6 7
9 10
8 0
0 0
0 0
0 0
0 12
0 0
*/
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3604kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: