QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#240732#7103. Red Black Treepandapythoner#AC ✓582ms29980kbC++233.7kb2023-11-05 18:00:082023-11-05 18:00:08

Judging History

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

  • [2023-11-05 18:00:08]
  • 评测
  • 测评结果:AC
  • 用时:582ms
  • 内存:29980kb
  • [2023-11-05 18:00:08]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) int((a).size())

vector<vector<pair<int, ll>>> gr;
vector<bool> red;

vector<int> p;
vector<ll> h;
vector<int> closest;
vector<int> tin;
vector<int> tout;
int timer = 0;

void dfs(int v, int pr, int cl) {
    if (red[v]) {
        closest[v] = v;
    } else {
        closest[v] = cl;
    }
    tin[v] = timer++;
    for (auto [to, w] : gr[v]) {
        if (to == pr) continue;
        h[to] = h[v] + w;
        p[to] = v;
        dfs(to, v, closest[v]);
    }
    tout[v] = timer++;
}

const int LOG = 20;

vector<vector<int>> up;

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int p = LOG - 1; p >= 0; --p) {
        if (up[p][u] != -1 && !is_ancestor(up[p][u], v)) {
            u = up[p][u];
        }
    }
    return p[u];
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    red.assign(n, false);
    for (int i = 0; i < m; ++i) {
        int v;
        cin >> v;
        v--;
        red[v] = true;
    }
    gr.assign(n, {});
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        gr[u].emplace_back(v, w);
        gr[v].emplace_back(u, w);
    }

    timer = 0;
    p.assign(n, -1);
    h.assign(n, 0);
    closest.resize(n);
    tin.resize(n);
    tout.resize(n);
    dfs(0, -1, 0);

    up.assign(LOG, vector<int>(n, -1));
    up[0] = p;
    for (int p = 1; p < LOG; ++p) {
        for (int i = 0; i < n; ++i) {
            if (up[p - 1][i] != -1) {
                up[p][i] = up[p - 1][up[p - 1][i]];
            }
        }
    }

    while (q--) {
        int k;
        cin >> k;
        vector<int> v(k);
        for (int i = 0; i < k; ++i) {
            cin >> v[i];
            v[i]--;
        }
        int maxx = *max_element(v.begin(), v.end(), [&](int i, int j) {
            return h[i] - h[closest[i]] < h[j] - h[closest[j]];
        });
        ll other_max = 0;
        for (auto i : v) {
            if (closest[i] != closest[maxx]) {
                other_max = max(other_max, h[i] - h[closest[i]]);
            }
        }
        {
            vector<int> new_v;
            for (auto i : v) {
                if (!(closest[i] != closest[maxx] || red[i])) {
                    new_v.push_back(i);
                }
            }
            v = new_v;
        }
        // erase_if(v, [&](int i) {
        //     return closest[i] != closest[maxx] || red[i];
        // });
        if (v.empty()) {
            cout << "0\n";
            continue;
        }
        sort(rall(v), [&](int i, int j) {
            return h[i] < h[j];
        });
        int cur = v[0];
        ll best = h[maxx] - h[closest[maxx]];
        ll base = best;
        for (int i = 0; i < sz(v); ++i) {
            cur = lca(cur, v[i]);
            if (i != sz(v) - 1) {
                best = min(best, max(base - (h[cur] - h[closest[maxx]]), h[v[i + 1]] - h[closest[maxx]]));
            } else {
                best = min(best, base - (h[cur] - h[closest[maxx]]));
            }
        }
        cout << max(best, other_max) << '\n';
    }
}

int32_t main(){
    if(1){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    #ifdef LOCAL
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
    #endif
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

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

详细

Test #1:

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

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: 582ms
memory: 29980kb

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