QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#783591	#9570. Binary Tree	Dixiky_215	AC ✓	332ms	13112kb	C++20	7.5kb	2024-11-26 10:50:14	2024-11-26 10:50:16

Judging History

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

[2024-11-26 10:50:16]
评测

测评结果：AC
用时：332ms
内存：13112kb

查看

[2024-11-26 10:50:14]
提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+7;
int t,n;
int siz[MAXN],id[MAXN],tot=0;
int l_son[MAXN],r_son[MAXN],fa[MAXN];
int maxl[MAXN],rot,du[MAXN],now_num=0;
bool vis[MAXN];
void dfs(int x)
{
    siz[x]=1;
    id[++tot]=x;maxl[x]=0;
    if(l_son[x])
    {
        dfs(l_son[x]);
        siz[x]+=siz[l_son[x]];
        maxl[x]=max(maxl[x],siz[l_son[x]]);
    }
    if(r_son[x])
    {
        dfs(r_son[x]);
        siz[x]+=siz[r_son[x]];
        maxl[x]=max(maxl[x],siz[r_son[x]]);
    }
    maxl[x]=max(maxl[x],now_num-siz[x]);
    return;
}
int ask(int x,int y)
{
    int sss;
    cout<<"? "<<x<<" "<<y<<endl;
    cin>>sss;
    return sss;
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);cout.tie(0);
    
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>l_son[i]>>r_son[i];
            if(l_son[i]) du[l_son[i]]++,fa[l_son[i]]=i;
            if(r_son[i]) du[r_son[i]]++,fa[r_son[i]]=i;
        }
        for(int i=1;i<=n;i++) if(!du[i]) {rot=i;break;}
        now_num=n;
        while(1)
        {
            fa[rot]=0;
            tot=0;
            dfs(rot);
            if(tot==1)
            {
                cout<<"! "<<id[1]<<endl;
                break;
            }
            int minl=1e9,min_id;
            for(int i=1;i<=tot;i++)
            {
                int x=id[i];
                if(minl>maxl[x])
                {
                    minl=maxl[x];
                    min_id=x;
                }
            }
            int x=min_id;
            if(fa[x]==0)
            {
                if(l_son[x]&&r_son[x])
                {
                    int sss=ask(l_son[x],r_son[x]);
                    if(sss==0)
                    {
                        fa[l_son[x]]=0;
                        rot=l_son[x];
                        now_num=siz[rot];
                    }
                    else if(sss==2)
                    {
                        fa[r_son[x]]=0;
                        rot=r_son[x];
                        now_num=siz[rot];
                    }
                    else
                    {
                        cout<<"! "<<x<<endl;
                        break;
                    }
                }
                else if(l_son[x])
                {
                    int sss=ask(l_son[x],x);
                    if(sss==0) cout<<"! "<<l_son[x]<<endl;
                    else cout<<"! "<<x<<endl;
                    break;
                }
                else if(r_son[x])
                {
                    int sss=ask(r_son[x],x);
                    if(sss==0) cout<<"! "<<r_son[x]<<endl;
                    else cout<<"! "<<x<<endl;
                    break;
                }
            }
            else
            {
                if(l_son[x]&&r_son[x])
                {
                    int s1=siz[l_son[x]],s2=siz[r_son[x]],s3=now_num-siz[x];
                    int minl=min(s1,min(s2,s3));
                    if(minl==s3)
                    {
                        int sss=ask(l_son[x],r_son[x]);
                        if(sss==0)
                        {
                            fa[l_son[x]]=0;
                            rot=l_son[x];
                            now_num=siz[rot];
                        }
                        else if(sss==2)
                        {
                            fa[r_son[x]]=0;
                            rot=r_son[x];
                            now_num=siz[rot];
                        }
                        else
                        {
                            now_num-=siz[l_son[x]]+siz[r_son[x]];
                            l_son[x]=0;r_son[x]=0;
                        }
                    }
                    else if(s1==minl)
                    {
                        int sss=ask(r_son[x],fa[x]);
                        if(sss==0)
                        {
                            fa[r_son[x]]=0;
                            rot=r_son[x];
                            now_num=siz[rot];
                        }
                        else if(sss==2)
                        {
                            now_num-=siz[x];
                            if(l_son[fa[x]]==x) l_son[fa[x]]=0;
                            if(r_son[fa[x]]==x) r_son[fa[x]]=0;
                        }
                        else
                        {
                            now_num-=s3+s2;
                            rot=x;
                            fa[rot]=0;
                            r_son[x]=0;
                        }
                    }
                    else
                    {
                        int sss=ask(l_son[x],fa[x]);
                        if(sss==0)
                        {
                            fa[l_son[x]]=0;
                            rot=l_son[x];
                            now_num=siz[rot];
                        }
                        else if(sss==2)
                        {
                            now_num-=siz[x];
                            if(l_son[fa[x]]==x) l_son[fa[x]]=0;
                            if(r_son[fa[x]]==x) r_son[fa[x]]=0;
                        }
                        else
                        {
                            now_num-=s3+s1;
                            l_son[x]=0;
                            rot=x;
                            fa[rot]=0;
                        }
                    }

                }
                else if(l_son[x])
                {
                    int sss=ask(l_son[x],fa[x]);
                    if(sss==0)
                    {
                        fa[l_son[x]]=0;
                        rot=l_son[x];
                        now_num=siz[rot];
                    }
                    else if(sss==2)
                    {
                        now_num-=siz[x];
                        if(l_son[fa[x]]==x) l_son[fa[x]]=0;
                        if(r_son[fa[x]]==x) r_son[fa[x]]=0;
                    }
                    else
                    {
                        cout<<"! "<<x<<endl;
                        break;
                    }
                }
                else if(r_son[x])
                {
                    int sss=ask(r_son[x],fa[x]);
                    if(sss==0)
                    {
                        fa[r_son[x]]=0;
                        rot=r_son[x];
                        now_num=siz[rot];
                    }
                    else if(sss==2)
                    {
                        now_num-=siz[x];
                        if(l_son[fa[x]]==x) l_son[fa[x]]=0;
                        if(r_son[fa[x]]==x) r_son[fa[x]]=0;
                    }
                    else
                    {
                        cout<<"! "<<x<<endl;
                        break;
                    }
                }
                else
                {
                    int sss=ask(x,fa[x]);
                    if(sss==0) cout<<"! "<<x<<endl;
                    else cout<<"! "<<fa[x]<<endl;
                    break;
                }
            }
            for(int i=0;i<=tot;i++) siz[id[i]]=0,maxl[id[i]]=0;
        }
        for(int i=0;i<=n;i++)
        {
            siz[i]=fa[i]=maxl[i]=0;
            l_son[i]=r_son[i]=0;
            vis[i]=0;
            du[i]=0;
        }
        
    }
    return 0;
}
/*
1
5
0 0
1 5
2 4
0 0
0 0
*/

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 7804kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: 0

Accepted

time: 90ms

memory: 7816kb

input:

output:

result:

ok OK (5555 test cases)

Test #3:

score: 0

Accepted

time: 62ms

memory: 7776kb

input:

output:

result:

ok OK (600 test cases)

Test #4:

score: 0

Accepted

time: 120ms

memory: 13112kb

input:

output:

? 43991 70790
? 46637 98261
? 69452 58487
? 39509 59517
? 57474 54741
? 657 74598
? 9151 6159
? 35868 36942
? 528 36409
? 66747 37416
? 27728 95772
? 70205 7642
? 20147 11958
? 59682 22076
? 83246 16046
? 54741 83246
! 83246
? 5676 85780
? 39704 57748
? 58489 42043
? 30188 50842
? 36012 24131
? 1857...

result:

ok OK (2 test cases)

Test #5:

score: 0

Accepted

time: 78ms

memory: 9928kb

input:

output:

result:

ok OK (15 test cases)

Test #6:

score: 0

Accepted

time: 71ms

memory: 11396kb

input:

output:

? 2 1
! 1
? 1 2
? 4 1
! 4
? 8 3
? 5 8
? 2 5
! 5
? 3 4
? 13 2
? 16 13
? 9 16
! 9
? 12 30
? 11 6
? 1 18
? 32 1
? 2 32
! 32
? 60 3
? 15 63
? 52 12
? 43 58
? 47 43
? 2 47
! 2
? 80 113
? 16 115
? 63 112
? 25 50
? 81 89
? 11 81
? 114 11
! 114
? 90 113
? 248 20
? 8 130
? 58 142
? 239 182
? 192 161
? 244 19...

result:

ok OK (16 test cases)

Test #7:

score: 0

Accepted

time: 74ms

memory: 9972kb

input:

output:

result:

ok OK (15 test cases)

Test #8:

score: 0

Accepted

time: 54ms

memory: 7744kb

input:

output:

result:

ok OK (600 test cases)

Test #9:

score: 0

Accepted

time: 112ms

memory: 8352kb

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:

? 22163 50379
? 11838 79924
? 18079 15463
? 72017 29994
? 80147 27856
? 80763 26264
? 39876 84186
? 73287 34615
? 43462 43070
? 38721 85806
? 84940 93114
? 3443 79116
? 49016 68555
? 56289 87545
? 32426 3887
! 3887
? 42261 72481
? 84675 96633
? 2124 81852
? 13836 79494
? 80643 24965
? 38932 5573
? 5...

result:

ok OK (2 test cases)

Test #10:

score: 0

Accepted

time: 73ms

memory: 8124kb

input:

output:

result:

ok OK (15 test cases)

Test #11:

score: 0

Accepted

time: 69ms

memory: 8304kb

input:

output:

result:

ok OK (16 test cases)

Test #12:

score: 0

Accepted

time: 73ms

memory: 8380kb

input:

output:

result:

ok OK (15 test cases)

Test #13:

score: 0

Accepted

time: 53ms

memory: 7816kb

input:

output:

result:

ok OK (600 test cases)

Test #14:

score: 0

Accepted

time: 112ms

memory: 10756kb

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:

? 71188 96970
? 87538 6820
? 59029 32876
? 46360 20365
? 9490 49372
? 51870 93805
? 74496 96975
? 90932 266
? 99552 77780
? 24315 12293
? 74615 44540
? 6226 80477
? 39596 49924
? 37134 13568
? 12293 37134
? 28352 37134
! 28352
? 50499 6749
? 42167 37781
? 96466 36486
? 37783 33496
? 48920 28303
? 93...

result:

ok OK (2 test cases)

Test #15:

score: 0

Accepted

time: 72ms

memory: 9756kb

input:

output:

result:

ok OK (15 test cases)

Test #16:

score: 0

Accepted

time: 65ms

memory: 9908kb

input:

output:

result:

ok OK (16 test cases)

Test #17:

score: 0

Accepted

time: 75ms

memory: 9688kb

input:

output:

result:

ok OK (15 test cases)

Test #18:

score: 0

Accepted

time: 114ms

memory: 8568kb

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:

? 35226 52174
? 16093 26122
? 11494 10853
? 91694 11494
? 73088 90037
? 21572 90037
? 51091 91442
? 93596 7067
? 75096 14316
? 55875 75096
? 42793 96805
? 59747 42793
? 472 67072
? 64770 59747
! 92650
? 80592 36933
? 68004 50906
? 65219 73367
? 33796 20489
? 74041 19704
? 35779 74041
? 85560 35779
?...

result:

ok OK (2 test cases)

Test #19:

score: 0

Accepted

time: 332ms

memory: 7780kb

input:

output:

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

result:

ok OK (100000 test cases)

Extra Test:

score: 0

Extra Test Passed