QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#779918#7103. Red Black TreergnerdplayerAC ✓699ms24864kbC++234.1kb2024-11-24 22:47:202024-11-24 22:48:00

Judging History

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

  • [2024-11-24 22:48:00]
  • 评测
  • 测评结果:AC
  • 用时:699ms
  • 内存:24864kb
  • [2024-11-24 22:47:20]
  • 提交

answer

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

using i64 = long long;

struct HLD {
    int n, cur = 0;
    vector<int> sz, top, dep, par, tin, tout, seq;
    vector<vector<int>> adj;
    HLD(int n) : n(n), sz(n, 1), top(n), dep(n), par(n), tin(n), tout(n), seq(n), adj(n) {}
    void add_edge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
    void build(int root = 0) {
        top[root] = root, dep[root] = 0, par[root] = -1;
        dfs1(root), dfs2(root);
    }
    void dfs1(int u) {
        if (auto it = find(adj[u].begin(), adj[u].end(), par[u]); it != adj[u].end()) {
            adj[u].erase(it);
        }
        for (auto &v : adj[u]) {
            par[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            sz[u] += sz[v];
            if (sz[v] > sz[adj[u][0]]) { swap(v, adj[u][0]); }
        }
    }
    void dfs2(int u) {
        tin[u] = cur++;
        seq[tin[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        tout[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = par[top[u]];
            } else {
                v = par[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)]; }
    int jump(int u, int k) {
        if (dep[u] < k) { return -1; }
        int d = dep[u] - k;
        while (dep[top[u]] > d) { u = par[top[u]]; }
        return seq[tin[u] - dep[u] + d];
    }
    // u is v's ancestor
    bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tin[v] < tout[u]; }
    // root's parent is itself
    int rooted_parent(int r, int u) {
        if (r == u) { return u; }
        if (is_ancestor(r, u)) { return par[u]; }
        auto it = upper_bound(adj[u].begin(), adj[u].end(), r, [&](int x, int y) {
            return tin[x] < tin[y];
        }) - 1;
        return *it;
    }
    // rooted at u, v's subtree size
    int rooted_size(int r, int u) {
        if (r == u) { return n; }
        if (is_ancestor(u, r)) { return sz[u]; }
        return n - sz[rooted_parent(r, u)];
    }
    int rooted_lca(int r, int a, int b) { return lca(a, b) ^ lca(a, r) ^ lca(b, r); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;

    auto solve = [&]() {
        int n, m, q;
        cin >> n >> m >> q;

        constexpr i64 inf = 1e18;
        vector<i64> cost(n, inf), dep(n);
        for (int i = 0; i < m; i++) {
            int u;
            cin >> u;
            cost[--u] = 0;
        }

        vector<vector<pair<int, int>>> adj(n);
        HLD hld(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
            hld.add_edge(u, v);
        }
        hld.build();

        auto dfs = [&](auto dfs, int u) -> void {
            for (auto [v, w] : adj[u]) {
                if (v != hld.par[u]) {
                    cost[v] = min(cost[v], cost[u] + w);
                    dep[v] = dep[u] + w;
                    dfs(dfs, v);
                }
            }
        };
        dfs(dfs, 0);

        for (int i = 0; i < q; i++) {
            int k;
            cin >> k;
            vector<int> a(k);
            for (int j = 0; j < k; j++) {
                cin >> a[j];
                a[j]--;
            }
            sort(a.begin(), a.end(), [&](int u, int v) { return cost[u] > cost[v]; });

            i64 ans = cost[a[0]];
            int lca = a[0];
            i64 mx = 0;

            for (int j = 0; j < k; j++) {
                lca = hld.lca(lca, a[j]);
                mx = max(mx, dep[a[j]]);
                ans = min(ans, max(j == k - 1 ? 0 : cost[a[j + 1]], mx - dep[lca]));
            }

            cout << ans << '\n';
        }
    };
    
    while (t--) {
        solve();
    }
    
    return 0;
}

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

详细

Test #1:

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

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 699ms
memory: 24864kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed