QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#391168#7103. Red Black TreeKKT89AC ✓1958ms33800kbC++173.8kb2024-04-16 14:18:452024-04-16 14:18:45

Judging History

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

  • [2024-04-16 14:18:45]
  • 评测
  • 测评结果:AC
  • 用时:1958ms
  • 内存:33800kb
  • [2024-04-16 14:18:45]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

struct heavy_light_decomposition {
    int n;
    vector<vector<int>> G;
    vector<int> par, sz, in, nxt;

    heavy_light_decomposition(int n) : n(n), G(n), par(n), sz(n, 1), in(n), nxt(n) {}
    void add_edge(int x, int y) {
        G[x].push_back(y);
        G[y].push_back(x);
    }
    void build() {
        auto dfs1 = [&](auto self, int s, int p) -> void {
            for (int i = 0; i < (int)G[s].size(); ++i) {
                int t = G[s][i];
                if (t == p) {
                    swap(G[s][i--], G[s].back());
                    G[s].pop_back();
                } else {
                    par[t] = s;
                    self(self, t, s);
                    sz[s] += sz[t];
                    if (sz[t] > sz[G[s][0]]) {
                        swap(G[s][0], G[s][i]);
                    }
                }
            }
        };
        dfs1(dfs1, 0, -1);
        int id = 0;
        auto dfs2 = [&](auto self, int s) -> void {
            in[s] = id++;
            for (int t : G[s]) {
                if (t == G[s][0]) {
                    nxt[t] = nxt[s];
                } else {
                    nxt[t] = t;
                }
                self(self, t);
            }
        };
        dfs2(dfs2, 0);
    }
    int lca(int s, int t) {
        while (1) {
            if (in[s] > in[t]) swap(s, t);
            if (nxt[s] == nxt[t]) return s;
            t = par[nxt[t]];
        }
    }
};

void slv() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<bool> red(n);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        red[x - 1] = true;
    }
    map<pair<int, int>, int> edge;
    heavy_light_decomposition hld(n);
    for (int i = 0; i < n - 1; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x -= 1, y -= 1;
        edge[{x, y}] = edge[{y, x}] = z;
        hld.add_edge(x, y);
    }
    hld.build();
    vector<ll> cost(n), dist(n);
    auto dfs = [&](auto dfs, int s, ll sum, ll c) -> void {
        if (red[s]) c = 0;
        dist[s] = sum;
        cost[s] = c;
        for (int t : hld.G[s]) {
            dfs(dfs, t, sum + edge[{s, t}], c + edge[{s, t}]);
        }
    };
    dfs(dfs, 0, 0, 0);
    while (q--) {
        int k;
        cin >> k;
        vector<int> v(k);
        ll L = -1, R = 0;
        for (int i = 0; i < k; i++) {
            cin >> v[i];
            v[i] -= 1;
            R = max(R, cost[v[i]]);
        }
        sort(v.begin(), v.end(), [&](auto i, auto j) { return cost[i] > cost[j]; });
        vector<int> lca(v.size());
        lca[0] = v[0];
        for (int i = 1; i < v.size(); i++) {
            lca[i] = hld.lca(lca[i - 1], v[i]);
        }

        while (R - L > 1) {
            ll mid = (L + R) / 2;
            int id = -1;
            int j = 0;
            for (int i : v) {
                if (cost[i] <= mid) break;
                id = lca[j++];
            }
            bool ok = true;
            if (id != -1) {
                for (int i : v) {
                    if (cost[i] <= mid) continue;
                    if (dist[i] - dist[id] > mid) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) R = mid;
            else L = mid;
        }
        cout << R << "\n";
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        slv();
    }
}

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

详细

Test #1:

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

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: 1958ms
memory: 33800kb

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