QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#755601	#9570. Binary Tree	qiuuu	ML	2ms	6236kb	C++17	1.9kb	2024-11-16 17:44:05	2024-11-16 17:44:06

Judging History

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

[2024-11-16 17:44:06]
评测

测评结果：ML
用时：2ms
内存：6236kb

查看

[2024-11-16 17:44:05]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define PB push_back
const int N=100009;
int n,m,t,z1,z2,rt;
int sz[N];
vector<int> edge[N];
void dfs(int x,int fa)
{
	sz[x]=1;
	for(int i:edge[x])
	{
		if(i==fa) continue;
		dfs(i,x);
		sz[x]+=sz[i];
	}
}
void fd(int x,int fa)
{
	bool flg=1;
	for(int i:edge[x])
	{
		if(i==fa) continue;
		fd(i,x);
		if(sz[i]*2>sz[rt]) flg=0; 
	}
	if((sz[rt]-sz[x])*2>sz[rt]) flg=0;
	if(flg)
		if(z1) z2=x;
	else z1=x;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i=1;i<=N-5;i++) edge[i].clear();
		for(int i=1,x,y;i<=n;i++)
		{
			scanf("%d%d",&x,&y);
			if(x) edge[x].PB(i),edge[i].PB(x);
			if(y) edge[y].PB(i),edge[i].PB(y);
		}
		rt=1;
		while(1)
		{
			dfs(rt,0);
			z1=z2=0;
			fd(rt,0);
			if(sz[rt]==1)
			{
				printf("! %d\n",rt);
				fflush(stdout);
				break;
			}
			if(!z2)
			{
				printf("? %d %d\n",edge[z1].back(),edge[z1].end()[-2]);
				fflush(stdout);
				int x;
				scanf("%d",&x);
				if(x==0)
				{
					x=edge[z1].back();
					edge[z1].clear();
					edge[z1].PB(x);
					edge[x].erase(remove(edge[x].begin(),edge[x].end(),z1),edge[x].end());
					rt=x;
				}
				else if(x==2)
				{
					x=edge[z1].end()[-2];
					edge[z1].clear();
					edge[z1].PB(x);
					edge[x].erase(remove(edge[x].begin(),edge[x].end(),z1),edge[x].end());
					rt=x;
				}
				else
				{
					edge[z1].pop_back();
					edge[z1].pop_back();
					rt=z1;
				}
			}
			else
			{
				printf("? %d %d\n",z1,z2);
				fflush(stdout);
				int x;
				scanf("%d",&x);
				if(x==0) 
				{
					for(auto i=edge[z1].begin();;i++)
					{
						if(*i==z2)
						{
							edge[z1].erase(i);
							break;
						}
					}
					rt=z1;
				}
				else 
				{
					for(auto i=edge[z2].begin();;i++)
					{
						if(*i==z1)
						{
							edge[z2].erase(i);
							break;
						}
					}
					rt=z2;
				}
			}
		}
	}
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 6236kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Memory Limit Exceeded

input:

output: