QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#735792	#9570. Binary Tree	yzhx^#	AC ✓	400ms	13600kb	C++17	2.7kb	2024-11-11 21:42:02	2024-11-11 21:42:03

Judging History

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

[2024-11-11 21:42:03]
评测

测评结果：AC
用时：400ms
内存：13600kb

查看

[2024-11-11 21:42:02]
提交

answer

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>

const int N = 1e5;
int head[N + 2], nxt[N * 2 + 2], ver[N * 2 + 2], tot;
int n, v[N + 2], sz[N + 2], mx[N + 2], S, root;

void add(int x, int y) {
    tot++;
    nxt[tot] = head[x];
    ver[tot] = y;
    head[x] = tot;
}

void find(int x, int fa) {
    sz[x] = 1, mx[x] = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (y == fa || v[y]) continue;
        find(y, x);
        sz[x] += sz[y];
        mx[x] = std::max(mx[x], sz[y]);
    }
    mx[x] = std::max(mx[x], S - sz[x]);
    if (mx[x] < mx[root]) root = x;
}

void deal(int x) {
    v[x] = 1;

    std::vector<int> q;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = ver[i];
        if (v[y]) continue;
        q.push_back(y);
    }
    if (q.size() == 0) {
        std::cout << "! " << x << std::endl;
        std::cout.flush();
        return;
    } else if (q.size() == 1) {  // ?
        std::cout << "? "<<q[0] << " " << x << std::endl;
        std::cout.flush();
        int a;
        std::cin >> a;
        if (a == 0)
            std::cout << "! " << q[0] << std::endl;
        else
            std::cout << "! " << x << std::endl;
        std::cout.flush();
        return;
    } else {
        std::sort(q.begin(),q.end(),[&](int i , int j){
            return sz[i] > sz[j];
        });
        std::cout <<"? "<< q[0] << " " << q[1] << std::endl;
        std::cout.flush();
        int a;
        std::cin >> a;
        if (a == 1) {
            v[q[0]] = 1, v[q[1]] = 1, v[x] = 0;
            find(x, q[0]);
            S = sz[x], root = 0, mx[0] = 1e9;
            find(x, q[0]);
            deal(root);
        } else if (a == 0) {
            find(q[0], x);
            S = sz[q[0]], root = 0, mx[0] = 1e9;
            find(q[0], x);
            deal(root);
        } else {
            find(q[1], x);
            S = sz[q[1]], root = 0, mx[0] = 1e9;
            find(q[1], x);
            deal(root);
        }
    }
    std::cout.flush();
}

void solve() {
    std::cin >> n;
    tot = 0;
    for (int i = 1; i <= n + 1; i++) head[i] = v[i] = sz[i] = mx[i] = 0;
    for (int i = 1; i <= n; i++) {
        int a, b;
        std::cin >> a >> b;
        if (a) add(i, a), add(a, i);
        if (b) add(i, b), add(b, i);
    }
    // add(n, n + 1), add(n + 1, n);
    // root = n + 1;
    find(1, 0);
    S = sz[1], root = 0, mx[0] = 1e9;
    find(1, 0);
    deal(root);
}

int main() {
    int times;
    std::cin >> times;
    while (times--) {
        solve();
    }
    return 0;
}

/*
1
7
2 0
3 4
0 0
5 6
0 0
0 7
0 0

*/

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 5776kb

input:

output:

result:

ok OK (2 test cases)

Test #2:

score: 0

Accepted

time: 102ms

memory: 3900kb

input:

output:

result:

ok OK (5555 test cases)

Test #3:

score: 0

Accepted

time: 75ms

memory: 5572kb

input:

output:

result:

ok OK (600 test cases)

Test #4:

score: 0

Accepted

time: 178ms

memory: 13600kb

input:

output:

? 70790 43991
? 98065 36882
? 89400 44312
? 52881 29266
? 79632 4792
? 42596 60575
? 48047 49462
? 35653 89053
? 97401 5200
? 88604 36002
? 39621 70194
? 66655 42334
? 88973 98852
? 44977 99415
? 35161 43955
? 35161 44977
! 44977
? 44110 46352
? 63067 47168
? 38328 51576
? 75910 60860
? 42451 28720
...

result:

ok OK (2 test cases)

Test #5:

score: 0

Accepted

time: 98ms

memory: 8352kb

input:

output:

result:

ok OK (15 test cases)

Test #6:

score: 0

Accepted

time: 92ms

memory: 9020kb

input:

output:

result:

ok OK (16 test cases)

Test #7:

score: 0

Accepted

time: 101ms

memory: 9272kb

input:

output:

result:

ok OK (15 test cases)

Test #8:

score: 0

Accepted

time: 83ms

memory: 3800kb

input:

output:

result:

ok OK (600 test cases)

Test #9:

score: 0

Accepted

time: 128ms

memory: 6888kb

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 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: 78ms

memory: 5676kb

input:

output:

result:

ok OK (15 test cases)

Test #11:

score: 0

Accepted

time: 72ms

memory: 6460kb

input:

output:

result:

ok OK (16 test cases)

Test #12:

score: 0

Accepted

time: 82ms

memory: 5624kb

input:

output:

result:

ok OK (15 test cases)

Test #13:

score: 0

Accepted

time: 78ms

memory: 5832kb

input:

output:

result:

ok OK (600 test cases)

Test #14:

score: 0

Accepted

time: 149ms

memory: 10540kb

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
? 51870 93805
? 96975 74496
? 13426 43271
? 87378 71402
? 32442 1061
? 44393 53273
? 99484 63082
? 46975 84398
? 70960 38147
? 70960 46975
? 46975 15186
! 46975
? 50499 6749
? 17715 75012
? 31421 58179
? 64768 20076
? 64370 98628
? ...

result:

ok OK (2 test cases)

Test #15:

score: 0

Accepted

time: 76ms

memory: 6900kb

input:

output:

result:

ok OK (15 test cases)

Test #16:

score: 0

Accepted

time: 85ms

memory: 7908kb

input:

output:

result:

ok OK (16 test cases)

Test #17:

score: 0

Accepted

time: 85ms

memory: 8168kb

input:

output:

? 1 2
! 2
? 1 6
? 3 5
! 5
? 11 14
? 11 13
? 6 12
! 6
? 8 20
? 1 9
? 1 8
? 21 28
! 21
? 59 42
? 2 15
? 16 52
? 16 15
? 15 62
! 62
? 17 40
? 102 11
? 119 110
? 15 67
? 15 119
? 117 73
! 117
? 189 90
? 65 224
? 229 10
? 57 98
? 16 15
? 15 67
? 217 56
! 217
? 192 60
? 44 285
? 151 36
? 435 451
? 122 429...

result:

ok OK (15 test cases)

Test #18:

score: 0

Accepted

time: 142ms

memory: 6696kb

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

result:

ok OK (2 test cases)

Test #19:

score: 0

Accepted

time: 400ms

memory: 5624kb

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