QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#735872#9570. Binary Treez_123WA 3ms18164kbC++142.8kb2024-11-11 22:15:012024-11-11 22:15:01

Judging History

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

  • [2024-11-11 22:15:01]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:18164kb
  • [2024-11-11 22:15:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N=1000020;
int e[N],ne[N],h[N],idx;
int f[N][2],g[N],d[N],du[N];
bool st[N];
void add(int x,int y)
{
	e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void dfs(int x,int y)
{
	f[x][0]=f[x][1]=0;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(v==y||st[v]) continue;
		dfs(v,x);
		if(f[v][1]+1>f[x][1])
		{
			f[x][0]=f[x][1];
			g[x]=v;
			f[x][1]=f[v][1]+1;
		}
		else if(f[v][1]+1>f[x][0])
			f[x][0]=f[v][1]+1;
	}
}
void dfs_1(int x,int y,int u)
{
	d[x]=max(f[x][1],u);
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(v==y||st[v]) continue;
		if(v!=g[x]) dfs_1(v,x,max(u+1,f[x][1]+1));
		else dfs_1(v,x,max(u+1,f[x][0]+1));
	}
}
int dfs_sum(int x,int y)
{
	int s=0;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(v==y||st[v]) continue;
		s+=dfs_sum(v,x);
	}
	return s+1; 
}
void dfs_er(int x,int y)
{
	st[x]=true;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int v=e[i];
		du[v]--;
		if(v==y||st[v]) continue;
		dfs_er(v,x);
	}
}
signed main()
{
	int t,n,i,j,x,y;
	cin>>t;
	while(t--)
	{
		cin>>n;
		idx=0;
		for(i=1;i<=n;i++)
		{
			h[i]=-1;
			du[i]=0;
			st[i]=false;
		}
		for(i=1;i<=n;i++)
		{
			cin>>x>>y;
			if(x!=0)
			{
				du[x]++;
				du[i]++;
				add(i,x);
				add(x,i);
			}
			if(y!=0)
			{
				du[y]++;
				du[i]++;
				add(i,y);
				add(y,i);
			}
		}
		while(1)
		{
			for(i=1;i<=n;i++)
				if(!st[i])
					break;
			int u=i,op;
			dfs(u,-1);
			dfs_1(u,-1,0);
			int mx=1e9,md=100;
			for(i=1;i<=n;i++)
				if(!st[i]&&(d[i]<mx||(d[i]==mx&&du[i]>md)))
				{
					mx=d[i];
					md=du[i];
					u=i;
				}
//			cout<<u<<' '<<d[u]<<"\n";
			if(du[u]==0)
			{
				cout<<"! "<<u<<endl;
				break;
			}
			else if(du[u]==1)
			{
				int v;
				for(i=h[u];i!=-1;i=ne[i])
					if(!st[e[i]])
					{
						v=e[i];
						break;
					}
				cout<<"? "<<u<<' '<<v<<endl;
				cin>>op;
				if(op==0) cout<<"! "<<u<<endl;
				else cout<<"! "<<v<<endl;
				break;
			}
			else if(du[u]==2)
			{
				vector<int>v;
				for(i=h[u];i!=-1;i=ne[i])
					if(!st[e[i]])
						v.push_back(e[i]);
				cout<<"? "<<v[0]<<' '<<v[1]<<endl;
				cin>>op;
				if(op==1)
				{
					cout<<"! "<<u<<endl;
					break;
				}
				else if(op==0) dfs_er(u,v[0]);
				else dfs_er(u,v[1]);
			}
			else
			{
				vector<PII>v;
				for(i=h[u];i!=-1;i=ne[i])
					if(!st[e[i]])
						v.push_back({dfs_sum(e[i],u),e[i]});
				sort(v.begin(),v.end());
				reverse(v.begin(),v.end());
				int x=v[0].second;
				int y=v[1].second;
				cout<<"? "<<x<<' '<<y<<endl;
				cin>>op;
				if(op==0) dfs_er(u,x);
				else if(op==2) dfs_er(u,y);
				else
				{
					dfs_er(y,u);
					dfs_er(x,u);
				}
			}
		}
	}
	return 0;
}
/*
1
7 
5 3
0 0
2 4
0 7
0 6
0 0
0 0

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 15836kb

input:

2
5
0 0
1 5
2 4
0 0
0 0
1
0
2
0 2
0 0
2

output:

? 3 5
? 1 2
! 1
? 1 2
! 2

result:

ok OK (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 18164kb

input:

5555
8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4
0
0
2
8
0 0
1 4
2 0
0 0
7 8
0 0
3 0
6 0
0
1
0
8
5 8
0 0
1 7
0 0
0 0
4 2
0 0
6 0
0
1
2
5
4 5
3 1
0 0
0 0
0 0
0
2
8
0 0
0 0
5 6
0 0
1 4
2 0
3 8
0 0
0
0
5
3 0
5 1
0 0
0 0
4 0
0
2
5
5 0
0 0
0 0
3 0
2 4
0
0
3
3 0
1 0
0 0
2
2
2 0
0 0
0
3
2 3
0 0
0 0
2
10
2 8
9 7
0 0
...

output:

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

result:

wrong answer Too many queries (test case 20)