QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#770105	#9570. Binary Tree	eastcloud	TL	0ms	3464kb	C++20	2.5kb	2024-11-21 20:41:53	2024-11-21 20:41:53

Judging History

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

[2024-11-21 20:41:53]
评测

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

查看

[2024-11-21 20:41:53]
提交

answer


#include<bits/stdc++.h>

#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline

using namespace std;

#define N 300005

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void write(int x){
    if(x<0)x=-x,putchar('-');
    if(x/10)write(x/10);
    putchar(x%10+'0');
}

vi e[N];
int vis[N],siz[N],tot;
int rt,maxn;

void find_root(int x,int fa){
    int maxsiz=0;siz[x]=1;
    for(auto v:e[x]){
        if(v==fa || vis[v])continue;
        find_root(v,x);siz[x]+=siz[v];
        maxsiz=max(maxsiz,siz[v]);
    }
    maxsiz=max(maxsiz,tot-siz[x]);
    if(maxsiz<maxn)maxn=maxsiz,rt=x;
}

void solve(){
    int n=read();
    for(int i=1;i<=n;i++)e[i].clear(),vis[i]=0;
    for(int i=1;i<=n;i++){
        int ls=read(),rs=read();
        if(ls)e[i].pb(ls),e[ls].pb(i);
        if(rs)e[i].pb(rs),e[rs].pb(i);
    }
    int x=1,cnt=0;
    while(1){
        vi S;cnt++;
        assert(cnt<=__lg(n)+3);
        for(auto v:e[x])if(!vis[v])S.pb(v);
        if(!S.size()){cout<<"! "<<x<<endl;break;}
        find_root(x,0);rt=0;maxn=n+5;tot=siz[x];find_root(x,0);
        x=rt;S.clear();
        //cerr<<rt<<' '<<S.size()<<' '<<tot<<"**"<<endl;
        for(auto v:e[x])if(!vis[v])S.pb(v);
        if(S.size()==1){
            int v=e[x][0];
            cout<<"? "<<x<<' '<<v<<endl;int res;cin>>res;
            if(res==0)cout<<"! "<<x<<endl;
            else cout<<"! "<<v<<endl;break;
        }
        else if(S.size()==2){
            int u=S[0],v=S[1];
            cout<<"? "<<u<<' '<<v<<endl;int res;cin>>res;
            if(res==1){cout<<"! "<<x<<endl;break;}             
            else if(res==0)vis[x]=1,x=u;
            else vis[x]=1,x=v;
        }
        else{
            sort(all(S),[](int x,int y){return siz[x]>siz[y];});
            cout<<"? "<<S[0]<<' '<<S[1]<<endl;int res;cin>>res;
            if(res==1)vis[S[0]]=vis[S[1]]=1;
            else if(res==0)vis[x]=1,x=S[0];
            else vis[x]=1,x=S[1];
        }
    }
}

int main(){

    int T=read();while(T--)solve();
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3464kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: