QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378739#8575. Three Person Tree Gameucup-team2112#AC ✓72ms35232kbC++204.3kb2024-04-06 14:27:032024-04-06 14:27:03

Judging History

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

  • [2024-04-06 14:27:03]
  • 评测
  • 测评结果:AC
  • 用时:72ms
  • 内存:35232kb
  • [2024-04-06 14:27:03]
  • 提交

answer

#include <bits/stdc++.h>

struct HLD {
    int n;
    std::vector<int> sz, top, dep, parent, in, out, seq;
    std::vector<std::vector<int>> adj;
    int dfs_clock;
    
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        sz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        dfs_clock = 0;
        adj.assign(n, {});
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }

    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        
        sz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            sz[u] += sz[v];
            if (sz[v] > sz[adj[u][0]]) {
                std::swap(v, adj[u][0]);
            }
        }
    }

    void dfs2(int u) {
        in[u] = dfs_clock++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = dfs_clock;
    }
    
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    
    // jump from u to k-th ancester
    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }
        
        int d = dep[u] - k;
        
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        
        return seq[in[u] - dep[u] + d];
    }
    
    // check if u is ancester of v (include u == v)
    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    
    // root is u, find parent of v
    int rootedParent(int u, int v) {
        std::swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    
    // root is u, find size of subtree rooted at v
    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return sz[v];
        }
        return n - sz[rootedParent(u, v)];
    }

    // find the middle point of a, b, c
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

void solve(){
    int n;
    std::cin >> n;
    HLD hld(n);
    int a, b, c;
    std::cin >> a >> b >> c;
    a--, b--, c--;
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        hld.addEdge(u - 1, v - 1);
    }
    hld.work();
    while(true) {
        if (hld.dist(a, c) <= 1) {
            std::cout << "A\n";
            return;
        }
        int na = hld.rootedParent(c, a);
        if (hld.dist(na, b) <= 1) {
            na = a;
        }
        if (hld.dist(na, b) <= 1) {
            std::cout << "B\n";
            return;
        }
        int nb = hld.rootedParent(na, b);
        if (hld.dist(nb, c) <= 1) {
            nb = b;
        }
        if (hld.dist(nb, c) <= 1) {
            std::cout << "C\n";
            return;
        }
        int nc = hld.rootedParent(nb, c);
        if (hld.dist(nc, na) <= 1) {
            nc = c;
        }
        if (na == a && nb == b && nc == c) {
            std::cout << "DRAW\n";
            return;
        }
        a = na;
        b = nb;
        c = nc;
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

2
3
1 2 3
2 1
3 1
4
1 2 3
1 4
2 4
3 4

output:

A
DRAW

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 19ms
memory: 3608kb

input:

10000
20
2 12 1
16 15
3 2
16 17
14 13
11 12
9 8
10 9
18 17
6 5
18 19
13 12
5 4
7 6
20 19
14 15
3 4
11 10
1 2
8 7
20
12 13 1
18 13
12 11
19 15
17 16
10 14
4 2
15 11
6 5
3 2
4 13
20 8
11 9
3 7
14 16
5 8
5 4
9 6
10 3
1 2
17
2 17 15
9 10
5 4
9 8
2 11
6 7
8 7
13 4
2 3
6 15
5 6
17 8
2 1
3 4
16 7
14 5
3 12...

output:

A
B
C
B
DRAW
C
A
A
A
DRAW
C
B
B
B
DRAW
A
DRAW
A
C
DRAW
A
B
A
A
A
B
B
B
C
A
A
A
B
B
DRAW
C
DRAW
A
A
A
A
A
B
B
A
C
DRAW
A
B
A
B
DRAW
A
C
DRAW
A
B
C
DRAW
DRAW
A
A
A
DRAW
DRAW
B
B
B
A
DRAW
B
B
A
A
DRAW
B
A
A
B
DRAW
A
B
A
C
DRAW
A
B
A
A
A
B
B
B
A
A
B
B
A
C
DRAW
B
A
B
A
A
A
C
A
A
DRAW
A
A
C
A
DRAW
C
A
B
A...

result:

ok 10000 lines

Test #3:

score: 0
Accepted
time: 30ms
memory: 3928kb

input:

100
2000
455 1301 981
1508 1509
1242 1243
1261 1260
190 191
1981 1980
591 592
1792 1791
1726 1727
959 960
134 135
1193 1192
836 835
1803 1804
1577 1578
1548 1549
718 717
1294 1295
1116 1117
59 58
138 139
425 426
1168 1169
1963 1962
1025 1026
867 866
892 893
589 588
871 872
891 892
722 721
1711 1712
...

output:

C
A
A
B
DRAW
C
A
B
B
DRAW
B
C
B
A
DRAW
B
C
A
C
DRAW
C
B
A
C
DRAW
A
C
C
C
DRAW
B
A
A
C
DRAW
C
A
B
C
DRAW
B
A
B
A
DRAW
A
C
B
A
DRAW
B
C
C
C
DRAW
A
B
B
C
DRAW
C
B
C
A
DRAW
A
C
B
A
DRAW
B
A
B
A
DRAW
C
A
C
B
DRAW
A
B
C
C
DRAW
C
B
C
A
DRAW
B
A
C
B
DRAW
A
A
A
C
DRAW

result:

ok 100 lines

Test #4:

score: 0
Accepted
time: 62ms
memory: 35232kb

input:

1
200000
123236 117321 150583
47722 47723
103604 103605
48192 48191
19204 19205
3666 3667
190708 190709
111542 111541
16125 16124
164298 164299
55406 55405
62042 62041
42100 42101
40664 40663
131742 131743
105518 105517
24249 24250
174387 174388
29840 29841
164536 164537
54802 54803
6378 6377
97486 ...

output:

A

result:

ok single line: 'A'

Test #5:

score: 0
Accepted
time: 72ms
memory: 19488kb

input:

1
200000
151854 28266 141391
178840 177656
70949 127572
92675 174074
38426 55569
16718 64264
72596 171817
36908 36081
44793 65081
114199 93358
10460 36725
18563 26764
77047 29901
17769 39712
109495 141203
24130 37855
165153 135141
94225 107789
57603 49313
197306 48518
61030 57058
199291 42676
60161 ...

output:

B

result:

ok single line: 'B'

Test #6:

score: 0
Accepted
time: 63ms
memory: 27312kb

input:

1
200000
107496 54564 62204
75611 75612
33562 133562
66786 66785
35079 35078
40044 40045
99675 199675
121963 21963
15671 15672
3062 103062
71627 171627
27125 127125
30049 30048
63164 63165
183373 83373
51319 51320
99879 199879
36383 136383
89110 89109
7607 107607
20098 20099
57792 157792
100415 415
...

output:

B

result:

ok single line: 'B'

Test #7:

score: 0
Accepted
time: 54ms
memory: 19696kb

input:

1
200000
158505 85726 178357
30247 29809
107160 107392
84411 84297
80963 81018
64893 65118
194706 194894
8253 8478
47677 48197
120341 120487
68388 68653
41048 40580
128093 127913
118156 117983
97582 97422
166508 166267
171977 171895
108683 108912
102410 102283
130584 130479
75441 75592
145257 145092...

output:

A

result:

ok single line: 'A'

Test #8:

score: 0
Accepted
time: 14ms
memory: 3580kb

input:

10992
3
1 2 3
2 1
3 1
3
1 3 2
2 1
3 1
3
2 1 3
2 1
3 1
3
2 3 1
2 1
3 1
3
3 1 2
2 1
3 1
3
3 2 1
2 1
3 1
4
1 2 3
2 1
3 2
4 1
4
1 2 4
2 1
3 2
4 1
4
1 3 2
2 1
3 2
4 1
4
1 3 4
2 1
3 2
4 1
4
1 4 2
2 1
3 2
4 1
4
1 4 3
2 1
3 2
4 1
4
2 1 3
2 1
3 2
4 1
4
2 1 4
2 1
3 2
4 1
4
2 3 1
2 1
3 2
4 1
4
2 3 4
2 1
3 2
4 ...

output:

A
A
B
A
B
A
B
A
A
A
A
A
A
B
A
A
A
A
A
B
B
B
C
A
B
B
A
B
A
C
A
A
A
A
A
A
B
B
A
DRAW
A
DRAW
B
B
A
DRAW
A
DRAW
B
B
A
DRAW
A
DRAW
B
A
A
A
A
A
A
A
B
A
A
A
A
B
B
A
A
A
A
A
B
A
A
C
A
B
B
B
B
B
C
A
B
C
A
C
B
B
A
A
B
A
A
C
A
A
A
A
B
B
A
C
B
A
C
C
A
B
B
B
B
A
A
A
A
A
A
A
A
A
A
A
A
B
B
A
A
A
A
A
DRAW
A
A
DRAW
...

result:

ok 10992 lines

Test #9:

score: 0
Accepted
time: 26ms
memory: 3644kb

input:

22222
9
1 2 3
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 4
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 5
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 6
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 7
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 8
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 2 9
2 1
3 2
4 3
5 4
6 1
7 6
8 7
9 8
9
1 3 2
2 1
3 ...

output:

B
B
B
A
A
A
A
A
B
B
A
A
A
A
A
C
B
A
A
A
A
A
C
C
A
A
A
A
A
A
A
A
B
B
B
A
A
A
A
A
B
B
A
A
A
A
A
C
B
A
A
A
A
A
C
C
A
A
A
B
B
B
B
A
B
B
A
A
A
A
A
A
B
A
A
A
A
A
A
C
A
A
A
A
A
A
A
A
B
B
B
A
A
A
A
C
B
B
A
A
A
A
C
C
B
A
A
A
A
C
C
C
A
A
A
B
B
B
B
B
A
A
B
B
B
B
A
A
B
A
A
A
A
A
A
A
A
A
A
A
C
A
A
A
B
B
B
C
A
A
...

result:

ok 22222 lines

Extra Test:

score: 0
Extra Test Passed