QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378701#8575. Three Person Tree Gameucup-team2112#TL 0ms3636kbC++204.3kb2024-04-06 14:16:182024-04-06 14:16:19

Judging History

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

  • [2024-04-06 14:16:19]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3636kb
  • [2024-04-06 14:16:18]
  • 提交

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, a) <= 1) {
            nc = c;
        }
        if (na == a && nb == b && nc == c) {
            std::cout << "DRAW\n";
            return;
        }
    }
}

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Time Limit Exceeded

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:


result: