QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#755334	#9570. Binary Tree	Maxduan^#	RE	0ms	12956kb	C++20	2.9kb	2024-11-16 17:05:53	2024-11-16 17:05:53

Judging History

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

[2024-11-16 17:05:53]
评测

测评结果：RE
用时：0ms
内存：12956kb

查看

[2024-11-16 17:05:53]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
int siz[maxn],mx[maxn];
set<int>g[maxn];
int all;
int zx=0,mm=1e9;
int n;

void findrt(int u,int fa){
    siz[u]=1;
    mx[u]=0;
    for(auto v:g[u]){
        if(v==fa)continue;
        findrt(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
    mx[u]=max(mx[u],all-siz[u]);
    if(mx[u]<mm){
        zx=u;
        mm=mx[u];
    }
}

void dfs(int u,int fa){
    siz[u]=1;
    for(auto v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}

/*

2
2 3
0 0
0 0

*/

void solve(){
    cin>>n;
    all=n;
    for(int i=1;i<=n;i++){
        int a,b;cin>>a>>b;
        if(a){
            g[i].insert(a);
            g[a].insert(i);
        }
        if(b){
            g[i].insert(b);
            g[b].insert(i);
        }
    }
    int Tmp=log2(n);
    zx=1;
    int cnt=0;
    while(1){
        mm=1e9;
        findrt(zx,0);
        dfs(zx,0);
        vector<int>vt;
        for(auto v:g[zx]){
            vt.push_back(v);
        }
        //cout<<"zx="<<zx<<'\n';
        
        if(vt.size()==3){
            assert(++cnt<=Tmp);
            cout<<"? "<<vt[0]<<' '<<vt[1]<<endl;
            int ans;cin>>ans;
            if(ans==1){
                all-=siz[vt[0]]+siz[vt[1]];
                g[zx].erase(vt[0]);
                g[zx].erase(vt[1]);
                continue;
            }

            if(ans==2){
                swap(vt[0],vt[1]);
            }
            all-=siz[zx]-siz[vt[0]];
            g[vt[0]].erase(zx);
            zx=vt[0];
        }
        else if(vt.size()==2){
            assert(++cnt<=Tmp);
            cout<<"? "<<vt[0]<<' '<<vt[1]<<endl;
            
            int ans;cin>>ans;
            if(all==3){
                if(ans==0){
                    cout<<"! "<<vt[0]<<endl;
                }
                else if(ans==2){
                    cout<<"! "<<vt[1]<<endl;
                }
                else cout<<"! "<<zx<<endl;
                return;
            }
            if(ans==1){
                cout<<"! "<<zx<<endl;
                return;
            }
            if(ans==2){
                swap(vt[0],vt[1]);
            }
            all-=siz[zx]-siz[vt[0]];
            g[vt[0]].erase(zx);
            zx=vt[0];
        }
        else if(vt.size()==1){
            assert(++cnt<=Tmp);
            cout<<"? "<<zx<<' '<<vt[0]<<endl;
            
            int ans;cin>>ans;
            if(ans==0){
                cout<<"! "<<zx<<endl;
            }
            else{
                cout<<"! "<<vt[0]<<endl;
            }
            return;
        }
        else{
            cout<<"! "<<zx<<endl;
            return;
        }
    }
    
}

signed main(){
    int TT=1;cin>>TT;
    while(TT--){
        solve();
        for(int i=1;i<=n;i++){
            g[i].clear();
        }
    }
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 12956kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Runtime Error

input:

output: