QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156861#7103. Red Black Treeucup-team135#AC ✓1847ms32520kbC++202.5kb2023-09-02 14:29:112023-09-02 14:55:52

Judging History

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

  • [2023-09-02 14:55:52]
  • 评测
  • 测评结果:AC
  • 用时:1847ms
  • 内存:32520kb
  • [2023-09-02 14:29:11]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long
#define all(x) x.begin(), x.end()
#ifdef LOCAL
#define debug(x) cerr << #x << ' ' << x << endl;
#else
#define debug(x)
#endif // LOCAL
using namespace std;

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n, m, q;
        cin >> n >> m >> q;
        vector<bool> r(n);
        for (int j = 0; j < m; ++j) {
            int x;
            cin >> x;
            --x;
            r[x] = 1;
        }
        vector<vector<pair<int, int>>> g(n);
        for (int i = 1; i < n; ++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> a(n), d(n), dw(n);
        int lg = __lg(n);
        vector<vector<int>> up(lg + 1, vector<int>(n));
        auto dfs = [&](auto dfs, int cur, int prev, int top) -> void {
            if (r[cur]) top = 0;
            up[0][cur] = prev;
            a[cur] = top;
            for (auto [nxt, w] : g[cur]) {
                if (nxt == prev) continue;
                d[nxt] = d[cur] + 1;
                dw[nxt] = dw[cur] + w;
                dfs(dfs, nxt, cur, top + w);
            }
        };
        dfs(dfs, 0, 0, 0);
        for (int lvl =1; lvl <= lg; ++lvl) {
            for (int cur = 0; cur < n; ++cur) up[lvl][cur] = up[lvl - 1][up[lvl - 1][cur]];
        }
        auto lca = [&](int u, int v) {
            for (int k = lg; k >= 0; --k) if (d[up[k][u]] >= d[v]) u = up[k][u];
            for (int k = lg; k >= 0; --k) if (d[up[k][v]] >= d[u]) v = up[k][v];
            for (int k = lg; k >= 0; --k) if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
            if (u == v) return u; else return up[0][u];
        };
        for (int j = 0; j < q; ++j) {
            int k;
            cin >> k;
            vector<int> x(k);
            for (int &v : x) cin >> v, --v;
            sort(all(x), [&](int u, int v){return a[u] > a[v];});
            int ans = a[x[0]];
            int l = x[0];
            int mxdw = dw[l];
            for (int i = 0; i < k; ++i) {
                l = lca(l, x[i]);
                mxdw = max(mxdw, dw[x[i]]);
             //   debug(mxdw);
              //  debug(l);
                ans = min(ans, max(i + 1 == k ? 0LL : a[x[i + 1]], mxdw - dw[l]));
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

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

详细

Test #1:

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

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: 1847ms
memory: 32520kb

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