QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#715096	#9570. Binary Tree	OIer_kzc^#	TL	1ms	3628kb	C++17	2.6kb	2024-11-06 10:25:34	2024-11-06 10:25:35

Judging History

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

[2024-11-06 10:25:35]
评测

测评结果：TL
用时：1ms
内存：3628kb

查看

[2024-11-06 10:25:34]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<" = "<<(x)<<'\n'
bool no[100005],del[100005];
int cnt,ls[100005],rs[100005],siz[100005];
void dfs1(int u){
    siz[u]=1;
    if(ls[u]) dfs1(ls[u]),siz[u]+=siz[ls[u]];
    if(rs[u]) dfs1(rs[u]),siz[u]+=siz[rs[u]];
}
void dele(int u,int skip){
    del[u]=1,cnt--;
    if(ls[u]&&ls[u]^skip) dele(ls[u],skip);
    if(rs[u]&&rs[u]^skip) dele(rs[u],skip);
}
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n,cnt=n;
        for(int i=1;i<=n;i++) del[i]=0;
        for(int i=1;i<=n;i++) cin>>ls[i]>>rs[i];
        bool yes=0;
        while(cnt>1){
            for(int i=1;i<=n;i++) no[i]=0;
            for(int i=1;i<=n;i++) if(!del[i]) no[ls[i]]=no[rs[i]]=1;
            int rt,fa=0;
            for(int i=1;i<=n;i++) if(!del[i]&&!no[i]) rt=i;
            dfs1(rt);
            int now=rt;
            while(max(siz[ls[now]],siz[rs[now]])>siz[rt]>>1){
                fa=now;
                if(siz[ls[now]]>siz[rt]>>1) now=ls[now];else now=rs[now];
            }
            if(cnt==2){
                cout<<"? "<<now<<' '<<(ls[now]|rs[now])<<endl;
                int t;cin>>t;
                if(!t) cout<<"! "<<now<<endl;
                else cout<<"! "<<(ls[now]|rs[now])<<endl;
                yes=1;break;
            }
            else if(!fa){
                cout<<"? "<<ls[now]<<' '<<rs[now]<<endl;
                int t;cin>>t;
                if(!t) dele(now,ls[now]),ls[now]=0;
                else if(t==1){
                    cout<<"! "<<now<<endl,yes=1;break;
                }
                else if(t==2) dele(now,rs[now]),rs[now]=0;
            }
            else if(ls[now]){
                cout<<"? "<<fa<<' '<<ls[now]<<endl;
                int t;cin>>t;
                if(!t){
                    dele(now,0);
                    if(ls[fa]==now) ls[fa]=0;else rs[fa]=0;
                }
                if(t==1){
                    dele(rt,now),dele(ls[now],0),ls[now]=0;
                }
                if(t==2) dele(rt,ls[now]);
            }
            else if(rs[now]){
                cout<<"? "<<fa<<' '<<rs[now]<<endl;
                int t;cin>>t;
                if(!t){
                    dele(now,0);
                    if(rs[fa]==now) rs[fa]=0;else ls[fa]=0;
                }
                if(t==1){
                    yes=1,cout<<"! "<<now<<endl;break;
                }
                if(t==2) dele(rt,rs[now]);
            }
        }
        if(!yes) for(int i=1;i<=n;i++) if(!del[i]) cout<<"! "<<i<<endl;
    }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3628kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: -100

Time Limit Exceeded

input:

output: