QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#159305#7103. Red Black Treeucup-team1631#AC ✓1503ms42976kbC++206.4kb2023-09-02 17:45:352023-09-02 17:45:37

Judging History

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

  • [2023-09-02 17:45:37]
  • 评测
  • 测评结果:AC
  • 用时:1503ms
  • 内存:42976kb
  • [2023-09-02 17:45:35]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
    return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
    return a > b ? (a = b, 1) : 0;
}

class LCA {
   public:
    LCA() = default;
    LCA(const std::vector<std::vector<int>>& G, int root)
        : G(G), LOG(32 - __builtin_clz(G.size())), depth(G.size()) {
        int V = G.size();
        table.assign(LOG, std::vector<int>(V, -1));

        dfs(root, -1, 0);

        for (int k = 0; k < LOG - 1; ++k) {
            for (int v = 0; v < V; ++v) {
                if (table[k][v] >= 0) {
                    table[k + 1][v] = table[k][table[k][v]];
                }
            }
        }
    }

    int query(int u, int v) const {
        if (depth[u] > depth[v]) std::swap(u, v);

        // go up to the same depth
        for (int k = 0; k < LOG; ++k) {
            if ((depth[v] - depth[u]) >> k & 1) {
                v = table[k][v];
            }
        }
        if (u == v) return u;

        for (int k = LOG - 1; k >= 0; --k) {
            if (table[k][u] != table[k][v]) {
                u = table[k][u];
                v = table[k][v];
            }
        }
        return table[0][u];
    }

    int dist(int u, int v) const {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }

    int parent(int v, int k) const {
        for (int i = LOG - 1; i >= 0; --i) {
            if (k >= (1 << i)) {
                v = table[i][v];
                k -= 1 << i;
            }
        }
        return v;
    }

    int jump(int u, int v, int k) const {
        int l = query(u, v);
        int du = depth[u] - depth[l];
        int dv = depth[v] - depth[l];
        if (du + dv < k) return -1;
        if (k < du) return parent(u, k);
        return parent(v, du + dv - k);
    }

   protected:
    const std::vector<std::vector<int>>& G;
    const int LOG;
    std::vector<std::vector<int>> table;
    std::vector<int> depth;

    void dfs(int v, int p, int d) {
        table[0][v] = p;
        depth[v] = d;
        for (int c : G[v]) {
            if (c != p) dfs(c, v, d + 1);
        }
    }
};

template <typename M>
class BinaryLifting : public LCA {
    using T = typename M::T;

   public:
    BinaryLifting() = default;
    BinaryLifting(const std::vector<std::vector<int>>& G,
                  const std::vector<T> vs, int root)
        : LCA(G, root) {
        int V = G.size();
        val.assign(LOG, std::vector<int>(V, M::id()));
        val[0] = vs;

        for (int k = 0; k < LOG - 1; ++k) {
            for (int v = 0; v < V; ++v) {
                if (table[k][v] >= 0) {
                    val[k + 1][v] = M::op(val[k][v], val[k][table[k][v]]);
                }
            }
        }
    }

    T fold(int u, int v) const {
        bool flipped = false;
        if (depth[u] > depth[v]) {
            std::swap(u, v);
            flipped = true;
        }
        T resu = M::id(), resv = M::id();

        // go up to the same depth
        for (int k = 0; k < LOG; ++k) {
            if ((depth[v] - depth[u]) >> k & 1) {
                resv = M::op(resv, val[k][v]);
                v = table[k][v];
            }
        }
        if (u == v) {
            resu = M::op(val[0][u], M::flip(resv));
            if (flipped) resu = M::flip(resu);
            return resu;
        }

        for (int k = LOG - 1; k >= 0; --k) {
            if (table[k][u] != table[k][v]) {
                resu = M::op(resu, val[k][u]);
                resv = M::op(resv, val[k][v]);
                u = table[k][u];
                v = table[k][v];
            }
        }
        resu = M::op(M::op(resu, val[0][table[0][u]]), M::flip(resv));
        if (flipped) resu = M::flip(resu);
        return resu;
    }

   private:
    std::vector<std::vector<T>> val;
};

struct AddMonoid {
    using T = int;
    static T id() { return 0; }
    static T op(T a, T b) { return a + b; }
    static T flip(T x) { return x; }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int T;
    cin >> T;
    while (T--) {
        int n, m, q;
        cin >> n >> m >> q;
        vector<int> red(n);
        rep(i, 0, m) {
            int r;
            cin >> r;
            --r;
            red[r] = 1;
        }
        vector<vector<pair<int, ll>>> G(n);
        vector<vector<int>> tree(n);
        rep(_, 0, n - 1) {
            int u, v, w;
            cin >> u >> v >> w;
            --u, --v;
            G[u].push_back({v, w});
            G[v].push_back({u, w});
            tree[u].push_back(v);
            tree[v].push_back(u);
        }

        // calculate the distance to the nearest red ancestor
        vector<ll> cost(n);

        auto dfs = [&](auto& dfs, int v, int p, ll x) -> void {
            if (red[v]) x = 0;
            cost[v] = x;
            for (auto [c, w] : G[v]) {
                if (c == p) continue;
                dfs(dfs, c, v, x + w);
            }
        };

        dfs(dfs, 0, -1, 0);

        LCA lca(tree, 0);
        BinaryLifting<AddMonoid> bl(tree, red, 0);

        while (q--) {
            int k;
            cin >> k;
            vector<pair<ll, int>> vs(k);
            rep(i, 0, k) {
                int v;
                cin >> v;
                --v;
                vs[i] = {cost[v], v};
            }

            // process in the descending order of the current cost
            sort(all(vs));
            reverse(all(vs));
            vs.push_back({0, -1});

            ll ans = vs[0].first;
            int l = vs[0].second;

            rep(i, 0, k) {
                auto [c, v] = vs[i];
                int nl = lca.query(l, v);

                // check if nl can become the nearest red for all v
                if (bl.fold(nl, l) + bl.fold(nl,v) > 0) {
                    break;
                }
                l = nl;
                chmin(ans, max(vs[0].first - cost[l], vs[i + 1].first));
            }
            cout << ans << "\n";
        }
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

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: 1503ms
memory: 42976kb

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