QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#734076	#9570. Binary Tree	xly_tyty^#	RE	1ms	3624kb	C++23	2.3kb	2024-11-10 23:44:25	2024-11-10 23:44:26

Judging History

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

[2024-11-10 23:44:26]
评测

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

查看

[2024-11-10 23:44:25]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+10;
int st[N],root,siz[N];
int n,m,k,x,w;
vector<int>p[N];
int query(int a,int b)
{
	if(!a)a++;
	if(!b)b++;
	cout<<'?'<<' '<<a<<' '<<b<<endl;
	int x;cin>>x;
	return x;
}
pii ans;
int mx,ty=0;
void dfs(int u,int fa)
{
	siz[u]=1;
	int l=0,r=0;
	for(int x:p[u])
	{
		if(st[x]||x==fa)continue;
		if(l==0)l=x;
		else if(r==0)r=x;
		dfs(x,u);
		siz[u]+=siz[x];
	}
	if(l!=0&&r==0)
	{
		int res=min(siz[l],n-siz[l]);
		if(res>mx)
		{
			mx=res;
			ans={u,l};
			ty=0;
		}
	}
	else if(l!=0&&r!=0)
	{
		int res=max({siz[l],siz[r],n-siz[l]-siz[r]});
		res=n-res;
		if(res>mx)
		{
			mx=res;
			ans={l,r};
			ty=u;
		}
	}
}
void solve()
{
	cin>>n;
	m=n;
	for(int i=0;i<=n+10;i++)p[i].clear(),st[i]=0;
	for(int i=1;i<=n;i++)
	{
		int l,r;cin>>l>>r;
		if(l)p[i].push_back(l),p[l].push_back(i);
		if(r)p[i].push_back(r),p[r].push_back(i);
	}
	root=1;
	int ct=2;
	while(1)
	{
		mx=0;
		ty=0;
		ans={0,0};
		dfs(root,0);
		int l=ans.first,r=ans.second;
		int cnt = 0;
		//int t=0;
		if(n==3)
		{
			int ll=0,rr=0;
			for(int x:p[root])
			{
				if(st[x])continue;
				cnt++;
				if(ll==0)ll=x;
				else if(rr==0)rr=x;
			}
			//cout<<root<<' '<<ll<<' '<<rr<<endl;
			if(cnt!=2)
			{
				root=ll;
				continue;
			}
		}
		int x=query(l,r);
		ct*=2;
		if(n==2)
		{
			if(!x)cout<<'!'<<' '<<l<<endl;
			else cout<<'!'<<' '<<r<<endl;
			return;
		}
		else if(n==3)
		{
			if(!x)cout<<'!'<<' '<<l<<endl;
			else if(x==1)cout<<'!'<<' '<<root<<endl;
			else cout<<'!'<<' '<<r<<endl;
			return;
		}
		//cout<<n<<endl;
		if(!ty)
		{
			if(!x)st[ans.second]=1,n-=siz[ans.second],root=ans.first;
			else st[ans.first]=1,n=siz[ans.second],root=ans.second;
			//cout<<ans.second<<' '<<siz[ans.second]<<endl;
		}
		else{
			if(!x)st[ty]=1,st[r]=1,n=siz[ans.first],root=ans.first;
			else if(x==1)st[l]=1,st[r]=1,n-=siz[ans.first]+siz[ans.second],root=ty;
			else st[ty]=1,st[l]=1,n=siz[ans.second],root=ans.second;
		}
		if(n==1)
		{
			cout<<'!'<<' '<<root<<endl;return;
		}
		if(ct>m)
		{
			cout<<"CAONIMA"<<endl;return;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);	
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3624kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output:

? 8 6
? 5 4
? 4 3
! 4
? 3 7
? 5 8
? 5 7
! 7
? 5 8
? 4 2
? 6 8
! 6
? 4 5
? 3 1
! 3
? 6 7
? 1 4
? 5 3
! 5
? 2 5
? 3 2
! 1
? 2 4
? 5 1
! 1
? 3 2
! 1
? 1 2
! 2
? 2 3
! 3
? 9 7
? 4 3
? 6 5
! 7
? 1 2
! 1
? 7 5
? 2 1
? 2 6
! 6
? 5 10
? 7 1
? 7 9
! 9
? 3 4
? 1 7
? 8 2
! 2
? 1 2
! 2
? 3 6
? 1 7
CAONIMA