QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#732436	#9570. Binary Tree	quark404^#	AC ✓	296ms	22400kb	C++20	4.9kb	2024-11-10 14:31:52	2024-11-10 14:31:53

Judging History

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

[2024-11-10 14:31:53]
评测

测评结果：AC
用时：296ms
内存：22400kb

查看

[2024-11-10 14:31:52]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
vector<int> mp[200005];
void init()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        mp[i].clear();
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x != 0)
        {
            mp[x].push_back(i);
            mp[i].push_back(x);
        }
        if (y != 0)
        {
            mp[y].push_back(i);
            mp[i].push_back(y);
        }
    }
    return;
}
int query(int x, int y)
{
    cout << "? " << x << ' ' << y << endl;
    cout << flush;
    int tmp;
    cin >> tmp;
    return tmp;
}
void print_ans(int x)
{
    cout << "! " << x << endl;
    cout << flush;
    return;
}
set<pair<int, int>> ban;
vector<int> vised;
int siz[200005];
int from[200005];
void dfs_get_size(int x,int fa)
{
    vised.push_back(x);
    from[x]=fa;
    siz[x]=0;
    for(int y:mp[x])
    {
        if(y==fa) continue;
        if(ban.count({x,y})==1) continue;
        dfs_get_size(y,x);
        siz[x]+=siz[y];
    }
    siz[x]++;
}
const int INF=0x3f3f3f3f;
void solve()
{
    if (n == 1)
    {
        print_ans(1);
        return;
    }
    ban.clear();
    vised.clear();
    int can_cnt = 0;
    for (int i = 0; i <= 20; i++)
    {
        if ((1ll << i) <= n)
            can_cnt = i;
        else
            break;
    }
    siz[0]=0;
    from[0]=0;
    int ans=-1;
    int root=1;
    for(int i=can_cnt;i>=1;i--)
    {
        vised.clear();
        dfs_get_size(root,0);
        if(siz[root]==1)
        {
            ans=root;
            break;
        }
        for(int x:vised)
        {
//            cout<<"nowx="<<x<<endl;
            vector<pair<int,int>> near;
            for(int y:mp[x])
            {
                if(ban.count({x,y})==1) continue;
                if(y==from[x])
                    near.push_back({y,siz[root]-siz[x]});
                else near.push_back({y,siz[y]});
            }
            assert(near.size()<=3&&near.size()>0);
            int limit=((1ll<<i)-1);
            bool failed=false;
            for(int j=0;j<near.size();j++)
                if(near[j].second>limit)
                {
                    failed=true;
                    break;
                }
            if(failed==true) continue;
            // cout<<"x="<<x<<endl;
            // cout<<"near.size="<<near.size()<<endl;
            if(near.size()==1)
            {
                int y=near[0].first;
                int k=query(x,y);
                ban.insert({x,y});
                ban.insert({y,x});
                if(k==0) root=x;
                else if(k==2) root=y;
                else assert(false);
                break;
            }
            else if(near.size()==2)
            {
                int y=near[0].first,z=near[1].first;
                int k=query(y,z);
                ban.insert({x,y});
                ban.insert({y,x});
                ban.insert({x,z});
                ban.insert({z,x});
                if(k==1) root=x;
                else if(k==0) root=y;
                else if(k==2) root=z;
                else assert(false);
                break;
            }
            else if(near.size()==3)
            {
                int minv=INF;
                int minpos=-1;
                for(int j=0;j<near.size();j++)
                {
                    auto [y,cnt]=near[j];
                    if(cnt<minv)
                    {
                        minv=cnt;
                        minpos=j;
                    }
                }
                // cout<<"near:"<<endl;
                // for(int j=0;j<near.size();j++)
                // {
                //     auto [y,cnt]=near[j];
                //     cout<<y<<' '<<cnt<<endl;
                // }
                // cout<<"minpos="<<minpos<<endl;
                near[minpos].second++;
                near[minpos].first=root;
                int y,z;
                if(minpos==0) y=near[1].first,z=near[2].first;
                if(minpos==1) y=near[0].first,z=near[2].first;
                if(minpos==2) y=near[0].first,z=near[1].first;
                // cout<<"y,z="<<y<<" "<<z<<endl;
                int k=query(y,z);
                ban.insert({x,y});
                ban.insert({y,x});
                ban.insert({x,z});
                ban.insert({z,x});
                if(k==1) root=x;
                else if(k==0) root=y;
                else if(k==2) root=z;
                break;
            }
            else assert(false);
        }
    }
    //check 1
    dfs_get_size(root,0);
    if(siz[root]==1) ans=root;
    if(ans!=-1) print_ans(ans);
    else while(true);
    return;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        init();
        solve();
    }
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5620kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: 0

Accepted

time: 74ms

memory: 8284kb

input:

output:

result:

ok OK (5555 test cases)

Test #3:

score: 0

Accepted

time: 51ms

memory: 5716kb

input:

output:

result:

ok OK (600 test cases)

Test #4:

score: 0

Accepted

time: 100ms

memory: 22400kb

input:

output:

? 21832 43704
? 6971 71188
? 30458 63382
? 4304 93568
? 361 37874
? 9251 26340
? 15585 42013
? 25838 91382
? 997 95184
? 54153 90126
? 16353 95841
? 27550 77553
? 67839 5731
? 81712 93286
? 12935 72635
? 81712 72635
! 6699
? 86419 11993
? 85348 54998
? 12254 9029
? 20746 66376
? 12059 3912
? 77842 4...

result:

ok OK (2 test cases)

Test #5:

score: 0

Accepted

time: 65ms

memory: 13284kb

input:

output:

result:

ok OK (15 test cases)

Test #6:

score: 0

Accepted

time: 65ms

memory: 14128kb

input:

output:

result:

ok OK (16 test cases)

Test #7:

score: 0

Accepted

time: 62ms

memory: 13744kb

input:

output:

result:

ok OK (15 test cases)

Test #8:

score: 0

Accepted

time: 34ms

memory: 7812kb

input:

output:

result:

ok OK (600 test cases)

Test #9:

score: 0

Accepted

time: 74ms

memory: 13972kb

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
? 18129 4652
? 11838 89914
? 9095 91827
? 42477 2178
? 35602 55790
? 67244 60938
? 3202 66638
? 68335 98564
? 33529 73935
? 36124 48516
? 78628 7732
? 69403 18726
? 62360 66017
? 73409 32345
? 92424 81769
! 73409
? 28897 96633
? 78976 42261
? 94970 92936
? 32997 84214
? 63614 49614
? 8...

result:

ok OK (2 test cases)

Test #10:

score: 0

Accepted

time: 48ms

memory: 10064kb

input:

output:

result:

ok OK (15 test cases)

Test #11:

score: 0

Accepted

time: 48ms

memory: 11508kb

input:

output:

? 1 2
! 2
? 4 2
? 4 3
! 4
? 3 5
? 5 7
? 6 4
! 4
? 16 15
? 6 12
? 8 10
? 8 13
! 8
? 1 14
? 3 32
? 22 21
? 28 20
? 7 17
! 17
? 1 45
? 58 37
? 19 40
? 63 55
? 5 50
? 52 13
! 50
? 1 106
? 92 13
? 75 21
? 122 47
? 67 112
? 98 34
? 35 72
! 35
? 30 191
? 245 3
? 199 243
? 66 123
? 52 201
? 215 255
? 249 27...

result:

ok OK (16 test cases)

Test #12:

score: 0

Accepted

time: 43ms

memory: 11164kb

input:

output:

result:

ok OK (15 test cases)

Test #13:

score: 0

Accepted

time: 54ms

memory: 5760kb

input:

output:

result:

ok OK (600 test cases)

Test #14:

score: 0

Accepted

time: 86ms

memory: 19504kb

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:

? 25670 86830
? 27705 12118
? 34820 91439
? 37202 35531
? 82680 26126
? 64838 22055
? 73050 11523
? 56221 53041
? 86126 10520
? 31090 81379
? 31752 26164
? 32385 5421
? 24565 93057
? 78745 5271
? 5271 37716
? 55010 18716
! 18716
? 22682 43830
? 7212 95957
? 34464 41887
? 13389 55869
? 92898 35382
? ...

result:

ok OK (2 test cases)

Test #15:

score: 0

Accepted

time: 57ms

memory: 13080kb

input:

output:

result:

ok OK (15 test cases)

Test #16:

score: 0

Accepted

time: 55ms

memory: 13396kb

input:

output:

result:

ok OK (16 test cases)

Test #17:

score: 0

Accepted

time: 51ms

memory: 13832kb

input:

output:

result:

ok OK (15 test cases)

Test #18:

score: 0

Accepted

time: 81ms

memory: 13212kb

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:

? 51763 13322
? 57914 41486
? 57914 21726
? 93208 82363
? 21507 88655
? 49575 22873
? 80059 31411
? 31411 56439
? 44277 38000
? 38000 50612
? 8452 20498
? 45911 73433
? 73433 42183
? 42722 42183
? 42722 36125
? 36125 55005
! 36125
? 80592 36933
? 68004 50906
? 73367 20489
? 58198 49952
? 77738 33839...

result:

ok OK (2 test cases)

Test #19:

score: 0

Accepted

time: 296ms

memory: 5728kb

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