QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#248005#7103. Red Black Treeucup-team2190WA 1146ms46996kbC++204.7kb2023-11-11 16:58:252023-11-11 16:58:25

Judging History

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

  • [2023-11-11 16:58:25]
  • 评测
  • 测评结果:WA
  • 用时:1146ms
  • 内存:46996kb
  • [2023-11-11 16:58:25]
  • 提交

answer

/**
 *  - Meet Brahmbhatt
 *  - Hard work always pays off
**/
#include"bits/stdc++.h"
using namespace std;

#ifdef MeetBrahmbhatt
#include "debug.h"
#else
#define dbg(...) 72
#endif

#define endl "\n"
#define int long long

const long long INF = 4e18;


template <int LOGN>
struct Lca {
    int n;
    vector<int> dep;
    vector<int> PAR;
    vector<int> L, R;
    vector<vector<pair<int, int>>> G;
    vector<vector<int>> up;
    int T = 0;
    Lca(const vector<vector<pair<int, int>>> &adj) {
        n = (int) adj.size();
        PAR.resize(n);
        dep.resize(n);
        L.resize(n);
        R.resize(n);
        G = adj;
        up.assign(LOGN, vector<int>(n, -1));
        dfs(0, -1);
    }
    inline void dfs (int u, int par) {
        PAR[u] = par;
        L[u] = T++;
        for (int i = 1; i < LOGN; i++) {
            if (up[i - 1][u] != -1) {
                up[i][u] = up[i - 1][up[i - 1][u]];
            }
        }
        for (auto &[to, w] : G[u]) {
            if (to != par) {
                up[0][to] = u;
                dep[to] = dep[u] + 1;
                dfs(to, u);
            }
        }
        R[u] = T;
    }
    bool is_ancestor(int u, int v) const {
        return L[u] <= L[v] && R[v] <= R[u];
    }
    inline int kth(int u, int k) {
        for (int i = 0; i < LOGN; i++) {
            if (k >> i & 1) {
                u = up[i][u];
                if (u == -1) {
                    return -1ll;
                }
            }
        }
        return u;
    }
    inline int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        int d = dep[x] - dep[y];
        x = kth(x, d);
        if (x == y) return x;
        for (int i = LOGN - 1; i >= 0; i--) {
            if (up[i][x] != up[i][y]) {
                x = up[i][x];
                y = up[i][y];
            }
        }
        return up[0][x];
    }
    inline int dis(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
};


void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> red(n);
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        red[x - 1] = 1;
    }

    vector<vector<pair<int, int>>> G(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    vector<int> ances(n);
    vector<int> cost(n);
    vector<int> dep(n);

    function<void(int, int, int)> dfs = [&] (int u, int par, int prev) {
        if (red[u]) {
            prev = u;
            cost[u] = 0;
        }
        ances[u] = prev;
        for (auto [to, w] : G[u]) {
            if (to != par) {
                cost[to] = cost[u] + w;
                dep[to] = dep[u] + w;
                dfs(to, u, prev);
            }
        }
    };
    dfs(0, -1, 0);

    Lca<20> T(G);
    while (q--) {
        int K;
        cin >> K;
        vector<int> nodes(K);
        for (int &i : nodes) {
            cin >> i;
            i--;
        }
        int mx = nodes[0];
        for (int i = 0; i < K; i++) {
            if (cost[nodes[i]] > cost[mx]) {
                mx = nodes[i];
            }
        }
        vector<int> sub;
        int other = 0;
        for (int i = 0; i < K; i++) {
            if (ances[nodes[i]] == ances[mx]) {
                sub.push_back(nodes[i]);
            } else {
                other = max(other, cost[nodes[i]]);
            }
        }
        int sz = (int) sub.size();

        vector<int> I(sz);
        iota(I.begin(), I.end(), 0);
        sort(I.begin(), I.end(), [&] (int x, int y) {return T.L[sub[x]] < T.L[sub[y]]; });

        vector<int> pref(sz + 1), suf(sz + 1);
        for (int i = 0; i < sz; i++) {
            pref[i + 1] = max(pref[i], cost[sub[I[i]]]);
        }
        for (int i = sz - 1; i >= 0; i--) {
            suf[i] = max(suf[i + 1], cost[sub[I[i]]]);
        }

        vector<int> Time;
        for (int i = 0; i < sz; i++) {
            Time.push_back(T.L[sub[I[i]]]);
        }

        int res = INF;
        for (int i = 0; i < sz; i++) {
            int z = T.lca(mx, sub[I[i]]);
            int nval = cost[mx] - (dep[z] - dep[ances[mx]]);
            int L = (int) (lower_bound(begin(Time), end(Time), T.L[z]) - begin(Time));
            int R = (int) (upper_bound(begin(Time), end(Time), T.R[z]) - begin(Time)) - 1;
            res = min(res, max({other, pref[L], suf[R + 1], nval}));
        }
        cout << res << endl;
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(9);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 1146ms
memory: 46996kb

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
873176972
621431667
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
1817...

result:

wrong answer 10th lines differ - expected: '1072765445', found: '873176972'