QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#762144	#9570. Binary Tree	nahida_qaq	AC ✓	297ms	20740kb	C++23	3.3kb	2024-11-19 13:55:30	2024-11-19 13:55:31

Judging History

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

[2024-11-19 13:55:31]
评测

测评结果：AC
用时：297ms
内存：20740kb

查看

[2024-11-19 13:55:30]
提交

answer

#include <bits/stdc++.h>
#define int long long
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
using namespace std;
const int N=1e6+5,mod1=1e9+7,mod2=998244353,inf=1e18;
typedef pair<int,int> pi;
void solve()
{
    int n;
    cin>>n;
    vector<vector<int>>g(n+5);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x)
        {
            g[i].pb(x);
            g[x].pb(i);
        }
        if(y)
        {
            g[i].pb(y);
            g[y].pb(i);
        }
    }
    vector<int>size(n+5),weight(n+5);
    vector<int>st(n+5);
    int centroid=1;
    int num=n;
    function<void(int,int)>dfs1=[&](int u,int fa)
    {
        size[u]=1;
        for(auto v:g[u])if(!st[v]&&v!=fa)
        {
            dfs1(v,u);
            size[u]+=size[v];
        }
    };
    function<void(int,int)>dfs2=[&](int u,int fa)
    {
        weight[u]=0;
        for(auto v:g[u])if(!st[v]&&v!=fa)
        {
            dfs2(v,u);
            weight[u]=max(weight[u],size[v]);
        }
        weight[u]=max(weight[u],num-size[u]);
        if(weight[u]<=num/2)centroid=u;
    };
    while(num>1)
    {
        dfs1(centroid,0);
        num=size[centroid];
        dfs2(centroid,0);
        int du=0;
        for(auto i:g[centroid])if(!st[i])du++;
        if(du==0)
        {
            cout<<'!'<<' '<<centroid<<endl;
            return ;
        }
        if(du==1)
        {
            int x=0;
            for(auto i:g[centroid])if(!st[i])
            {
                x=i;
                break;
            }
            cout<<'?'<<' '<<centroid<<' '<<x<<endl;
            int t;
            cin>>t;
            if(t==0)
            {
                cout<<'!'<<' '<<centroid<<endl;
                return ;
            }
            st[centroid]=1;
            centroid=x;
            continue;
        }
        if(du==2)
        {
            int x=0,y=0;
            for(auto i:g[centroid])if(!st[i])
            {
                if(!x)x=i;
                else
                {
                    y=i;
                    break;
                }
            }
            cout<<'?'<<' '<<x<<' '<<y<<endl;
            int t;
            cin>>t;
            if(t==1)
            {
                cout<<'!'<<' '<<centroid<<endl;
                return ;
            }
            if(t==0)
            {
                st[centroid]=st[y]=1;
                centroid=x;
                continue;
            }
            st[centroid]=st[x]=1;
            centroid=y;
            continue;
        }
        int x=g[centroid][0],y=g[centroid][1],z=g[centroid][2];
        int sx=size[x],sy=size[y],sz=size[z];
        if(sx<sy)swap(x,y),swap(sx,sy);
        if(sx<sz)swap(x,z),swap(sx,sz);
        if(sy<sz)swap(y,z),swap(sy,sz);
        cout<<'?'<<' '<<x<<' '<<y<<endl;
        int t;
        cin>>t;
        if(t==0)
        {
            st[centroid]=st[z]=st[y]=1;
            centroid=x;
            continue;
        }
        if(t==1)
        {
            st[x]=st[y]=1;
            continue;
        }
        st[centroid]=st[z]=st[x]=1;
        centroid=y;
        continue;
    }
}
signed main()
{
    io;
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

源文件, 语言: C++23

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3568kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: 0

Accepted

time: 89ms

memory: 4496kb

input:

output:

result:

ok OK (5555 test cases)

Test #3:

score: 0

Accepted

time: 52ms

memory: 3868kb

input:

output:

result:

ok OK (600 test cases)

Test #4:

score: 0

Accepted

time: 135ms

memory: 20740kb

input:

output:

? 70790 43991
? 36882 98065
? 17626 87676
? 23816 44703
? 44123 980
? 61196 90504
? 11034 54094
? 34051 63621
? 26980 79154
? 55857 22501
? 15747 28077
? 76840 35270
? 8937 97062
? 22539 61940
? 43281 70074
? 70074 79154
! 79154
? 5676 85780
? 39704 57748
? 42043 58489
? 50842 30188
? 24131 36012
? ...

result:

ok OK (2 test cases)

Test #5:

score: 0

Accepted

time: 70ms

memory: 12156kb

input:

output:

result:

ok OK (15 test cases)

Test #6:

score: 0

Accepted

time: 73ms

memory: 12300kb

input:

output:

result:

ok OK (16 test cases)

Test #7:

score: 0

Accepted

time: 79ms

memory: 12660kb

input:

output:

result:

ok OK (15 test cases)

Test #8:

score: 0

Accepted

time: 55ms

memory: 3692kb

input:

output:

result:

ok OK (600 test cases)

Test #9:

score: 0

Accepted

time: 95ms

memory: 12044kb

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:

? 69076 50379
? 79924 11838
? 79924 15463
? 4652 41708
? 18079 37031
? 88632 903
? 89674 67056
? 35681 26183
? 66747 51833
? 65443 37626
? 92136 82736
? 80802 55075
? 68266 86057
? 41319 58263
? 39886 24593
? 90236 28387
! 28387
? 72481 42261
? 96633 84675
? 96633 81852
? 93383 79494
? 2124 71702
? ...

result:

ok OK (2 test cases)

Test #10:

score: 0

Accepted

time: 59ms

memory: 9056kb

input:

output:

result:

ok OK (15 test cases)

Test #11:

score: 0

Accepted

time: 63ms

memory: 9040kb

input:

output:

result:

ok OK (16 test cases)

Test #12:

score: 0

Accepted

time: 59ms

memory: 9172kb

input:

output:

result:

ok OK (15 test cases)

Test #13:

score: 0

Accepted

time: 60ms

memory: 4040kb

input:

output:

result:

ok OK (600 test cases)

Test #14:

score: 0

Accepted

time: 113ms

memory: 17432kb

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
? 97012 17131
? 63260 47373
? 54267 50792
? 90948 40354
? 57900 28477
? 57947 45466
? 61749 49953
? 46253 74237
? 36006 80813
? 80813 50792
? 50792 66247
! 50792
? 86513 70265
? 36225 11800
? 25987 99536
? 63730 59217
? 84543 29352
...

result:

ok OK (2 test cases)

Test #15:

score: 0

Accepted

time: 62ms

memory: 10996kb

input:

output:

result:

ok OK (15 test cases)

Test #16:

score: 0

Accepted

time: 47ms

memory: 11084kb

input:

output:

result:

ok OK (16 test cases)

Test #17:

score: 0

Accepted

time: 67ms

memory: 11704kb

input:

output:

result:

ok OK (15 test cases)

Test #18:

score: 0

Accepted

time: 117ms

memory: 12148kb

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
? 41901 64770
? 41901 70941
! 70941
? 91773 80592
? 80592 50906
? 73367 65219
? 20489 33796
? 19704 74041
? 74041 35779...

result:

ok OK (2 test cases)

Test #19:

score: 0

Accepted

time: 297ms

memory: 3620kb

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