QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#766499	#5015. 树	yyyyxh	0	15ms	138284kb	C++20	1.8kb	2024-11-20 17:31:45	2024-11-20 17:31:47

Judging History

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

[2024-11-20 17:31:47]
评测

测评结果：0
用时：15ms
内存：138284kb

查看

[2024-11-20 17:31:45]
提交

answer

#include "tree.h"
#define ALL(vc) (vc).begin(), (vc).end()
using namespace std;
typedef vector<int> vi;
const int N = 1003;
mt19937 rng(random_device{}());
vector<int> vec[N];
int d[N][N];
bool ins[N];
int cur[N];
int f[1000003];
int sol(int x, vi vc) {
    if (vc.size() == 1lu)
        return vc.back();
    shuffle(ALL(vc), rng);
    for (int x : vc)
        cur[x] = 0;
    int mn = 0x3f3f3f3f;
    vi sub, pvc;
    for (int x : vc) {
        pvc.emplace_back(x);
        for (int y : vc)
            cur[y] += d[x][y];
        int mx = 0;
        for (int y : vc)
            ++f[cur[y]];
        for (int y : vc)
            if (f[cur[y]] > mx)
                mx = f[cur[y]];
        for (int y : vc)
            --f[cur[y]];
        if (mn > mx)
            mn = mx, sub = pvc;
    }
    int cur = ask(x, sub) - sub.size();
    vi tmp;
    for (int x : vc) {
        int now = 0;
        for (int y : sub)
            now += d[x][y];
        if (now == cur)
            tmp.emplace_back(x);
    }
    return sol(x, tmp);
}
void solver(int n, int A, int B) {
    for (int i = 1; i <= n; ++i)
        ins[i] = 0, vec[i].clear();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = 0;
    int rt = rng() % n + 1;
    for (int i = 1; i <= n; ++i)
        if (i != rt)
            vec[ask(rt, vi(1, i))].emplace_back(i);
    vec[0].emplace_back(rt);
    for (int i = 1; i <= n; ++i) {
        if (vec[i].empty())
            break;
        shuffle(ALL(vec[i]), rng);
        for (int x : vec[i]) {
            int y = sol(x, vec[i - 1]);
            answer(x, y);
            for (int t = 1; t <= n; ++t)
                if (ins[t])
                    d[t][x] = d[x][t] = d[y][t] + 1;
            ins[x] = 1;
        }
    }
}

源文件, 语言: C++20

详细

Subtask #1:

score: 0

Wrong Answer

Test #1:

score: 0

Wrong Answer

time: 15ms

memory: 138284kb

input:

1000 500000 500000
1 2
2 3
2 4
2 5
2 6
3 7
2 8
5 9
5 10
9 11
2 12
9 13
4 14
5 15
12 16
5 17
4 18
4 19
13 20
9 21
19 22
7 23
6 24
14 25
2 26
10 27
14 28
21 29
17 30
8 31
15 32
9 33
22 34
24 35
20 36
6 37
12 38
19 39
31 40
35 41
25 42
11 43
8 44
9 45
12 46
26 47
10 48
6 49
27 50
39 51
33 52
6 53
43 54...

output:

Too many queries

result:

wrong answer Wrong Answer

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 0

Wrong Answer

time: 2ms

memory: 11264kb

input:

100 3000 40000
66 95
66 60
66 93
66 69
66 82
66 24
66 64
66 84
66 42
66 22
66 67
66 54
66 90
66 26
66 41
66 18
66 43
66 68
66 36
66 88
66 33
66 29
66 79
66 6
66 48
66 47
66 8
66 38
66 61
69 97
64 30
38 86
88 14
18 10
54 81
88 25
29 2
18 21
95 46
42 80
93 91
61 62
68 35
47 23
69 17
93 28
18 31
61 70
...

output:

Too many queries

result:

wrong answer Wrong Answer

Subtask #3:

score: 0

Wrong Answer

Test #111:

score: 0

Wrong Answer

time: 8ms

memory: 26112kb

input:

1000 50000 3000000
126 207
937 126
615 937
837 615
500 837
588 500
505 588
353 505
60 353
904 60
656 904
685 656
460 685
614 460
551 614
537 551
858 537
596 858
9 596
738 9
918 738
322 918
940 322
859 940
113 859
110 113
312 110
995 312
443 995
246 443
257 246
238 257
999 238
885 999
976 885
330 976...

output:

Too many queries

result:

wrong answer Wrong Answer

Subtask #4:

score: 0

Wrong Answer

Test #211:

score: 0

Wrong Answer

time: 3ms

memory: 15444kb

input:

990 8500 300000
1 2
1 3
1 4
1 5
2 6
2 7
2 8
3 9
3 10
3 11
4 12
4 13
4 14
5 15
5 16
5 17
6 18
6 19
6 20
7 21
7 22
7 23
8 24
8 25
8 26
9 27
9 28
9 29
10 30
10 31
10 32
11 33
11 34
11 35
12 36
12 37
12 38
13 39
13 40
13 41
14 42
14 43
14 44
15 45
15 46
15 47
16 48
16 49
16 50
17 51
17 52
17 53
18 54
18...

output:

Too many queries

result:

wrong answer Wrong Answer