QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#744922	#9570. Binary Tree	Tolret	TL	2ms	3656kb	C++20	2.8kb	2024-11-14 00:24:42	2024-11-14 00:24:42

Judging History

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

[2024-11-14 00:24:42]
评测

测评结果：TL
用时：2ms
内存：3656kb

查看

[2024-11-14 00:24:42]
提交

answer

#include<bits/stdc++.h>
#define int long long int
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
// #define '\n' endl
using namespace std;
const int maxn=1e6+5;
const int inf=1e18;
int n;
vector<int>edge[maxn];
int sz[maxn];
bool vis[maxn];
int ask(int u,int v)
{
	cout<<"? "<<u<<' '<<v<<endl;
	int ans;cin>>ans;
	return ans;
}
void dfs(int x,int pre)
{
	sz[x]=1;
	for(auto j:edge[x])
	{
		if(j==pre||vis[j])continue;
		dfs(j,x);
		sz[x]+=sz[j];
	}
}
int u1=-1,v1=-1;
int tmp1,tmp2,tmp3;
void dfs3(int x,int pre)
{
	for(auto j:edge[x])
	{
		if(j==pre||vis[j])continue;
		if(sz[x]-sz[j]==sz[j])
		{
			u1=x,v1=j;return;
		}
		int sz1=sz[x],sz2=sz[j];
		sz[x]-=sz[j];
		sz[j]=sz[j]+sz[x];
		dfs3(j,x);
		sz[x]=sz1;
		sz[j]=sz2;
	}
}
int oo=-1;
void dfs4(int x,int pre)
{
	int maxp1=0,maxp2=0;
	for(auto j:edge[x])
	{
		if(j==pre||vis[j])continue;
		if(sz[j]>sz[maxp1])
		{
			swap(maxp1,maxp2);
			maxp1=j;
		}
		else if(sz[j]>sz[maxp2])
		{
			maxp2=j;
		}
	}
	if(maxp2==0)
	{

	}
	else if(u1==-1||(max({sz[maxp1],sz[maxp2],sz[x]-sz[maxp1]-sz[maxp2]})-min({sz[maxp1],sz[maxp2],sz[x]-sz[maxp1]-sz[maxp2]}))<(max({tmp1,tmp2,tmp3})-min({tmp1,tmp2,tmp3})))
	{
		u1=maxp1,v1=maxp2;oo=x;
		tmp1=sz[u1],tmp2=sz[v1],tmp3=sz[oo]-tmp1-tmp2;
	}
	for(auto j:edge[x])
	{
		if(j==pre||vis[j])continue;
		int sz1=sz[x],sz2=sz[j];
		sz[x]-=sz[j];
		sz[j]=sz[j]+sz[x];
		dfs4(j,x);
		sz[x]=sz1;
		sz[j]=sz2;
	}
}
void dfs2(int x,int pre)
{
	vis[x]=true;
	for(auto j:edge[x])
	{
		if(j==pre||vis[j])continue;
		dfs2(j,x);
	}
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		edge[i].clear();vis[i]=false;
	}
	for(int i=1;i<=n;i++)
	{
		int u,v;cin>>u>>v;
		if(u)
		{
			edge[u].pb(i);edge[i].pb(u);
		}
		if(v)
		{
			edge[v].pb(i);edge[i].pb(v);
		}
	}
	bool flag=true;
	while(flag)
	{
		int tmp=0;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				dfs(i,0);
				tmp=i;
				break;
			}
		}
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
				cnt++;
		}
		if(cnt==1)
		{
			cout<<"! "<<tmp<<endl;
			return;
		}
		u1=-1,v1=-1;
		dfs3(tmp,0);
		if(u1!=-1)
		{
			int uu=ask(u1,v1);
			if(uu==0)
			{
				dfs2(v1,u1);
			}
			else
			{
				dfs2(u1,v1);
			}
		}
		else
		{
			oo=-1;tmp1=tmp2=tmp3=0;
			dfs4(tmp,0);
			int uu=ask(u1,v1);
			if(uu==0)
			{
				dfs2(v1,oo);
				dfs2(oo,u1);
			}
			else if(uu==1)
			{
				dfs2(v1,oo);
				dfs2(u1,oo);
			}
			else
			{
				dfs2(u1,oo);
				dfs2(oo,v1);
			}
		}
	}
}
signed main()
{
	// ios::sync_with_stdio(false);
    // cin.tie(nullptr);
	// cout.tie(nullptr);
    // cout<<fixed<<setprecision(10);
	int T=1;
    cin>>T;
    for(int i=1;i<=T;i++)
    solve();
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 2ms

memory: 3656kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: