QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#772446	#9570. Binary Tree	F7487	TL	0ms	7736kb	C++14	2.7kb	2024-11-22 19:37:17	2024-11-22 19:37:17

Judging History

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

[2024-11-22 19:37:17]
评测

测评结果：TL
用时：0ms
内存：7736kb

查看

[2024-11-22 19:37:17]
提交

answer

#include<bits/stdc++.h>
#define maxn 400005
using namespace std;
int qread(){
	int s=0;char a=getchar();
	while(!isdigit(a))a=getchar();
	while(isdigit(a)){
		s=(s<<1)+(s<<3)+a-'0';
		a=getchar();
	}
	return s;
}
int cnt,head[maxn],siz[maxn],tot,son[5];
bool vis[maxn];
struct xs{
	int nxt,to;
}e[maxn];
void addn(int x,int y){
	e[++cnt].nxt=head[x];head[x]=cnt;
	e[cnt].to=y;return;
}
void dfs_ini(int x,int f){
	int i,v;
	siz[x]=1;tot++;
	for(i=head[x];i;i=e[i].nxt){
		v=e[i].to;
		if(vis[v])continue;
		if(v==f)continue;
		else{
			dfs_ini(v,x);siz[x]+=siz[v];
		}
	}
	return;
}
int pos;
void dfs_core(int x,int f){
	int i,v;bool bl=1;
	for(i=head[x];i;i=e[i].nxt){
		v=e[i].to;
		if(vis[v])continue;
		if(v==f)continue;
		if(siz[v]>tot/2){
			bl=0;dfs_core(v,x);
		}
		if(pos)break;
	}
	if(bl)pos=x;
	return;	
}
int main(){
	int T=qread(),I,n,x,y,p,v,cts,ans,st,i,j=0,s1,s2,s3;
	for(I=1;I<=T;I++){
	    n=qread();cnt=0;ans=0;
	    for(i=1;i<=n;i++){
	    	head[i]=siz[i]=vis[i]=0;
	    }
		for(i=1;i<=n;i++){
			x=qread();y=qread();
			if(x){
				addn(i,x);addn(x,i);
			}
			if(y){
				addn(i,y);addn(y,i);
			}
		}	
		pos=1;j=0;
		while(1){
			j++;
			p=pos;pos=0;tot=0;
			dfs_ini(p,0);dfs_core(p,0);cts=0;
			for(i=head[pos];i;i=e[i].nxt){
				v=e[i].to;if(vis[v])continue;
				son[++cts]=v;
			}
		    if(cts==3){
		    	s1=siz[son[1]];s2=siz[son[2]];s3=siz[son[3]];
		    	if(siz[son[1]]>siz[pos])s1-=siz[pos];
		    	if(siz[son[2]]>siz[pos])s2-=siz[pos];
		    	if(siz[son[3]]>siz[pos])s3-=siz[pos];
		    	if(s2==max(s1,max(s2,s3)))swap(son[1],son[2]);
		    	if(s3==max(s1,max(s2,s3)))swap(son[1],son[3]);
		    	cout<<"? "<<son[1]<<" "<<son[2]<<'\n';cout.flush();
		    	st=qread();if(st==0){
		    		vis[pos]=1;pos=son[1];
		    	}
		    	else{
		    		if(st==1){
		    			vis[son[1]]=1;vis[son[2]]=1;
		    		}
		    		else{
		    			vis[pos]=1;pos=son[2];
		    		}
		    	}		    				    	
		    }
		    else{
		    	if(cts==2){
		    		cout<<"? "<<son[1]<<" "<<son[2]<<'\n';cout.flush();
		    		st=qread();if(st==0){
		    			vis[pos]=1;pos=son[1];
		    		}
		    		else{
		    			if(st==1){
		    				ans=pos;break;
		    			}
		    			else{
		    				vis[pos]=1;pos=son[2];
		    			}
		    		}		    		
		    	}
		    	else{
		    		if(cts==1){
		    			cout<<"? "<<pos<<" "<<son[1]<<'\n';cout.flush();
		    			st=qread();if(st==0){
		    				ans=pos;break;
		    			}
		    			else{
		    				ans=son[1];break;
		    			}
		    		}
		    		else{
		    			ans=pos;break;
		    		}
		    	}
		    }
		    if(j>100000)break;
		}
		cout<<"! "<<ans<<'\n';cout.flush();
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 7736kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: