QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#731682	#9570. Binary Tree	TheZone	AC ✓	289ms	8108kb	C++20	7.8kb	2024-11-10 10:27:53	2024-11-10 10:28:01

Judging History

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

[2024-11-10 10:28:01]
评测

测评结果：AC
用时：289ms
内存：8108kb

查看

[2024-11-10 10:27:53]
提交

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(siz[ls[now]]>siz[rs[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{
                cout<<"? "<<fa<<' '<<rs[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(rs[now],0),rs[now]=0;
                }
                if(t==2) dele(rt,rs[now]);
            }
        }
        if(!yes) for(int i=1;i<=n;i++) if(!del[i]) cout<<"! "<<i<<endl;
    }
}
/*#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(siz[ls[now]]>siz[rs[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{
                cout<<"? "<<fa<<' '<<rs[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(rs[now],0),rs[now]=0;
                }
                if(t==2) dele(rt,rs[now]);
            }
        }
        if(!yes) for(int i=1;i<=n;i++) if(!del[i]) cout<<"! "<<i<<endl;
    }
}#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(siz[ls[now]]>siz[rs[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{
                cout<<"? "<<fa<<' '<<rs[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(rs[now],0),rs[now]=0;
                }
                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++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3608kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: 0

Accepted

time: 73ms

memory: 3776kb

input:

output:

result:

ok OK (5555 test cases)

Test #3:

score: 0

Accepted

time: 56ms

memory: 3576kb

input:

output:

result:

ok OK (600 test cases)

Test #4:

score: 0

Accepted

time: 131ms

memory: 8108kb

input:

output:

? 70790 43991
? 98065 36882
? 44312 89400
? 59529 53895
? 65419 5852
? 14311 82041
? 47722 90087
? 45190 18514
? 97549 7166
? 74597 3775
? 21857 21630
? 75156 92329
? 25297 10672
? 29165 20974
? 75800 26030
? 26030 21857
! 21857
? 85780 5676
? 57748 39704
? 42043 58489
? 50842 30188
? 24131 36012
? ...

result:

ok OK (2 test cases)

Test #5:

score: 0

Accepted

time: 71ms

memory: 6508kb

input:

output:

result:

ok OK (15 test cases)

Test #6:

score: 0

Accepted

time: 77ms

memory: 6644kb

input:

output:

result:

ok OK (16 test cases)

Test #7:

score: 0

Accepted

time: 72ms

memory: 6512kb

input:

output:

result:

ok OK (15 test cases)

Test #8:

score: 0

Accepted

time: 44ms

memory: 3620kb

input:

output:

result:

ok OK (600 test cases)

Test #9:

score: 0

Accepted

time: 115ms

memory: 4964kb

input:

2
99999
0 0
7999 97267
75750 37659
0 0
0 0
33761 92098
90707 18838
13602 27569
0 0
0 0
0 0
0 0
0 0
0 0
0 0
14586 86647
1519 23132
0 0
3430 14643
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
47066 36968
95308 38482
34100 25297
0 0
0 0
0 0
0 0
88902 58991
0 0
0 0
66315 68538
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0...

output:

? 50379 22163
? 79924 11838
? 79924 15463
? 4652 88632
? 18079 40612
? 41708 24579
? 63141 88436
? 54568 23667
? 96127 34342
? 59253 87905
? 71622 43885
? 89669 29947
? 58321 97575
? 99570 77326
? 73462 15443
? 61865 43088
! 43088
? 72481 42261
? 96633 84675
? 96633 81852
? 93383 79494
? 2124 37561
...

result:

ok OK (2 test cases)

Test #10:

score: 0

Accepted

time: 71ms

memory: 4516kb

input:

output:

result:

ok OK (15 test cases)

Test #11:

score: 0

Accepted

time: 75ms

memory: 4580kb

input:

output:

? 2 1
! 1
? 4 2
? 4 3
! 4
? 5 7
? 1 2
? 1 3
! 3
? 16 15
? 6 12
? 8 10
? 8 13
! 8
? 19 2
? 3 15
? 25 18
? 13 27
? 13 30
! 30
? 9 14
? 58 24
? 29 32
? 17 3
? 15 39
? 15 57
! 15
? 92 13
? 83 73
? 57 115
? 62 54
? 56 55
? 79 88
? 79 69
! 79
? 245 3
? 218 134
? 223 108
? 47 234
? 119 200
? 90 69
? 135 20...

result:

ok OK (16 test cases)

Test #12:

score: 0

Accepted

time: 73ms

memory: 4524kb

input:

output:

result:

ok OK (15 test cases)

Test #13:

score: 0

Accepted

time: 65ms

memory: 3588kb

input:

output:

result:

ok OK (600 test cases)

Test #14:

score: 0

Accepted

time: 124ms

memory: 6548kb

input:

2
99999
96748 53986
34197 77552
29863 63559
79099 26449
45078 1051
0 0
27416 4135
0 0
38606 81189
93892 68603
48776 185
79602 18311
51243 83678
89044 40032
28883 35663
0 0
0 0
21603 15821
0 0
51448 75971
70275 8326
0 0
0 0
57049 72937
3297 94939
0 0
59258 39159
3205 34675
54876 24769
0 0
0 0
0 0
851...

output:

? 96970 71188
? 6820 87538
? 32876 59029
? 20365 46360
? 49372 9490
? 93805 51870
? 96975 74496
? 87346 50053
? 22841 44535
? 62765 6517
? 93268 35799
? 91247 66059
? 4653 3600
? 73850 33733
? 33733 22841
? 22841 60354
! 22841
? 6749 50499
? 37781 42167
? 36486 96466
? 33496 37783
? 28303 48920
? 95...

result:

ok OK (2 test cases)

Test #15:

score: 0

Accepted

time: 76ms

memory: 5556kb

input:

output:

result:

ok OK (15 test cases)

Test #16:

score: 0

Accepted

time: 64ms

memory: 5532kb

input:

output:

result:

ok OK (16 test cases)

Test #17:

score: 0

Accepted

time: 78ms

memory: 5464kb

input:

output:

result:

ok OK (15 test cases)

Test #18:

score: 0

Accepted

time: 123ms

memory: 4988kb

input:

2
99999
0 0
88119 0
72740 0
6901 19702
0 0
10620 84889
0 0
9552 63972
45156 60768
9152 72379
0 0
59875 97207
48193 0
17282 54916
65927 27713
80083 15817
36966 75381
0 0
77279 56298
0 0
11554 61779
0 0
89976 0
65282 42151
95206 62876
97329 86772
0 0
0 0
0 0
11820 0
0 0
20432 0
50520 39907
0 0
46948 1...

output:

? 52174 35226
? 26122 16093
? 61873 11494
? 11494 91694
? 90037 73088
? 90037 21572
? 91442 51091
? 7067 93596
? 14316 75096
? 75096 55875
? 41734 42793
? 42793 59747
? 92650 67072
? 64770 41901
? 41901 70941
! 41901
? 36933 80592
? 80592 50906
? 73367 65219
? 20489 33796
? 19704 74041
? 74041 35779...

result:

ok OK (2 test cases)

Test #19:

score: 0

Accepted

time: 289ms

memory: 3624kb

input:

output:

? 2 1
! 1
? 2 1
! 2
? 2 1
! 1
? 2 1
! 2
? 2 1
! 1
? 2 1
! 2
? 2 1
! 2
? 2 1
! 2
? 2 1
! 2
? 2 1
! 1
? 2 1
! 2
? 2 1
! 2
? 2 1
! 1
? 2 1
! 1
? 2 1
! 2
? 2 1
! 1
? 2 1
! 1
? 2 1
! 1
? 2 1
! 1
? 2 1
! 2
? 2 1
! 2
? 2 1
! 2
? 2 1
! 1
? 2 1
! 2
? 2 1
! 2
? 2 1
! 1
? 2 1
! 1
? 2 1
! 1
? 2 1
! 1
? 2 1
! 1
...

result:

ok OK (100000 test cases)

Extra Test:

score: 0

Extra Test Passed