QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#753038	#9570. Binary Tree	forget-star^#	ML	1ms	5860kb	C++17	2.1kb	2024-11-16 11:02:58	2024-11-16 11:02:59

Judging History

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

[2024-11-16 11:02:59]
评测

测评结果：ML
用时：1ms
内存：5860kb

查看

[2024-11-16 11:02:58]
提交

answer

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
const int N=1e5+10;
int n,head[N],nxt[N<<1],to[N<<1],cnt,vis[N];
inline void add(int x,int y)
{
	++cnt;nxt[cnt]=head[x];
	head[x]=cnt;to[cnt]=y;
	return;
}
int dg[N],siz[N],tot,rt,mx[N];
void dfs(int x,int fa)
{
	siz[x]=1;mx[x]=0;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y]) continue;
		dg[x]++;
		if(y==fa) continue;
		dfs(y,x);
		siz[x]+=siz[y];
		mx[x]=max(mx[x],siz[y]);
	}
	mx[x]=max(tot-siz[x],mx[x]);
	if(!rt||mx[x]<mx[rt]) rt=x;
	return;
}
void del(int x,int fa)
{
	vis[x]=1;tot--;
	for(int i=head[x];i;i=nxt[i])
	{
		int y=to[i];
		if(vis[y]||y==fa) continue;
		del(y,x);
	}
	return;
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);cnt=0;tot=n;
		for(int i=1;i<=n;i++) head[i]=0;
		for(int i=1;i<=n;i++)
		{
			int x,y;scanf("%d%d",&x,&y);
			if(x!=0) add(i,x),add(x,i);
			if(y!=0) add(i,y),add(y,i);
		}
		for(int i=1;i<=n;i++) vis[i]=0;
		while(1)
		{
			for(int i=1;i<=n;i++) dg[i]=0;
			rt=0;
			for(int i=1;i<=n;i++)
				if(!vis[i])
				{
					dfs(i,0);
					break;
				}
			if(dg[rt]==0)
			{
				printf("! %d\n",rt);
				fflush(stdout);
				break;
			}
			else if(dg[rt]==1)
			{
				int y=0;
				for(int i=head[rt];i;i=nxt[i])
				{
					if(vis[to[i]]) continue;
					y=to[i];
				}
				printf("? %d %d\n",rt,y);
				fflush(stdout);
				int tmp;scanf("%d",&tmp);
				if(tmp==0)
				{
					printf("! %d\n",rt);
					fflush(stdout);
					break;
				}
				else
				{
					printf("! %d\n",y);
					fflush(stdout);
					break;
				}
			}
			else
			{
				int t1=0,t2=0;
				for(int i=head[rt];i;i=nxt[i])
				{
					if(vis[to[i]]) continue;
					if(!t1) t1=to[i];
					else if(!t2) t2=to[i];
				}
				printf("? %d %d\n",t1,t2);
				fflush(stdout);
				int tmp;scanf("%d",&tmp);
				if(tmp==0)
				{
					del(rt,t1);
				}
				else if(tmp==1)
				{
					del(t1,rt);
					del(t2,rt);
				}
				else
				{
					del(rt,t2);
				}
			}
		}
	}
	return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5860kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Memory Limit Exceeded

input:

output: