QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#158451#7103. Red Black Treeucup-team133#AC ✓1506ms30944kbC++235.4kb2023-09-02 16:32:422023-09-02 16:32:45

Judging History

This is the latest submission verdict.

  • [2023-09-02 16:32:45]
  • Judged
  • Verdict: AC
  • Time: 1506ms
  • Memory: 30944kb
  • [2023-09-02 16:32:42]
  • Submitted

answer

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

struct HeavyLightDecomposition {
    vector<vector<pair<int, int>>> G;
    int n, time;
    vector<int> par, sub, head, vid;
    vector<ll> dep;
    HeavyLightDecomposition(int n) : G(n), n(n), time(0), par(n, -1), sub(n), head(n), vid(n, -1), dep(n) {}

    void add_edge(int u, int v, int w) {
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }

    void build() {
        dfs_sz(0);
        head[0] = 0;
        dfs_hld(0);
    }

    int lca(int u, int v) {
        for (;; v = par[head[v]]) {
            if (vid[u] > vid[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }

    pair<unordered_map<int, vector<int>>, int> virtualtree(vector<int>& vs) {
        int sz = vs.size();
        sort(begin(vs), end(vs), [&](int i, int j) { return vid[i] < vid[j]; });
        for (int i = 0; i < sz - 1; i++) vs.emplace_back(lca(vs[i], vs[i + 1]));
        sort(begin(vs), end(vs), [&](int i, int j) { return vid[i] < vid[j]; });
        vs.erase(unique(begin(vs), end(vs)), end(vs));
        vector<int> s;
        unordered_map<int, vector<int>> res;
        for (int v : vs) {
            while (not s.empty() and vid[s.back()] + sub[s.back()] <= vid[v]) s.pop_back();
            if (not s.empty()) res[s.back()].emplace_back(v);
            s.emplace_back(v);
        }
        return {res, vs[0]};
    }

  private:
    void dfs_sz(int v) {
        sub[v] = 1;
        if (not G[v].empty() and G[v].front().first == par[v]) swap(G[v].front(), G[v].back());
        for (auto& p : G[v]) {
            int u = p.first;
            if (u == par[v]) continue;
            par[u] = v;
            dep[u] = dep[v] + p.second;
            dfs_sz(u);
            sub[v] += sub[u];
            if (sub[u] > sub[G[v].front().first]) swap(p, G[v].front());
        }
    }

    void dfs_hld(int v) {
        vid[v] = time++;
        for (auto& p : G[v]) {
            int u = p.first;
            if (u == par[v]) continue;
            head[u] = (u == G[v][0].first ? head[v] : u);
            dfs_hld(u);
        }
    }
};

constexpr ll INF = (1LL << 60) - 1;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<bool> red(n, false);
    for (; m--;) {
        int v;
        cin >> v;
        red[--v] = true;
    }
    HeavyLightDecomposition HLD(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        HLD.add_edge(--u, --v, w);
    }

    HLD.build();
    vector<bool> target(n, false);
    vector<ll> nxt(n);  // v の祖先であって最も近い赤までの距離
    auto& G = HLD.G;
    {
        auto dfs = [&](auto self, int v, int p, ll D) -> void {
            if (red[v]) D = 0;
            nxt[v] = D;
            for (auto [u, w] : G[v]) {
                if (u == p) continue;
                self(self, u, v, D + w);
            }
        };
        dfs(dfs, 0, -1, 0);
    }
    vector dp(n, vector<ll>(3, -INF));
    auto query = [&](vector<int> vs) -> ll {
        auto nvs = vs;
        if (nvs.front() != 0) nvs.insert(nvs.begin(), 0);
        auto [g, root] = HLD.virtualtree(nvs);
        for (int& v : vs) target[v] = true;
        auto dfs1 = [&](auto self, int v) -> void {
            for (int u : g[v]) {
                self(self, u);
                ll w = HLD.dep[u] - HLD.dep[v];
                dp[v][1] = max(dp[v][1], dp[u][1]);
                ll x = nxt[u];
                if (dp[u][0] >= 0 and x <= w)
                    dp[v][1] = max(dp[v][1], dp[u][0] + x);
                else
                    dp[v][0] = max(dp[v][0], dp[u][0] + (dp[u][0] >= 0 ? w : 0));
                dp[v][2] = max(dp[v][2], dp[u][2]);
            }
            if (target[v]) {
                dp[v][0] = max(dp[v][0], 0LL);
                dp[v][2] = max(dp[v][2], nxt[v]);
            }
            if (red[v]) {
                dp[v][1] = max(dp[v][1], dp[v][0]);
                dp[v][0] = -INF;
            }
        };
        dfs1(dfs1, root);
        ll ans = dp[root][2];
        auto dfs2 = [&](auto self, int v, ll D) -> void {
            vector<ll> vals;
            auto& ch = g[v];
            ans = min(ans, max({dp[v][0], dp[v][1], D}));
            if (target[v]) D = max(D, nxt[v]);
            int len = ch.size() + 1;
            for (int i = 0; i < len - 1; i++) vals.emplace_back(dp[ch[i]][2]);
            vals.emplace_back(D);
            vector<ll> left(len + 1), right(len + 1);
            left[0] = right[len] = -INF;
            for (int i = 0; i < len; i++) left[i + 1] = max(left[i], vals[i]);
            for (int i = len - 1; i >= 0; i--) right[i] = max(right[i + 1], vals[i]);
            for (int i = 0; i < len - 1; i++) self(self, ch[i], max(left[i], right[i + 1]));
        };
        dfs2(dfs2, root, -INF);
        for (int& v : vs) target[v] = false;
        for (int& v : nvs) {
            for (int i = 0; i < 3; i++) {
                dp[v][i] = -INF;
            }
        }
        return ans;
    };

    for (; q--;) {
        int k;
        cin >> k;
        vector<int> vs(k);
        for (int& v : vs) cin >> v, v--;
        cout << query(vs) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (; T--;) solve();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1506ms
memory: 30944kb

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