QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#166954#7103. Red Black TreePHarrAC ✓1309ms58360kbC++202.6kb2023-09-06 21:37:532023-09-06 21:37:53

Judging History

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

  • [2023-09-06 21:37:53]
  • 评测
  • 测评结果:AC
  • 用时:1309ms
  • 内存:58360kb
  • [2023-09-06 21:37:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

using pii = pair<int, int>;

const int inf = 1e15;


void solve() {
    int n, m, q, logN, dn = 0;
    cin >> n >> m >> q;
    vector<vector<pii>> e(n + 1), g(n + 1);
    vector<int> dfn(n + 1), dis(n + 1), dist(n + 1, LLONG_MAX);
    queue<int> que;
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        que.push(x), dist[x] = 0;
    }

    logN = log2(n);
    vector f(logN + 1, vector<int>(n + 1));

    for (int i = 1, x, y, z; i < n; i++)
        cin >> x >> y >> z , e[x].emplace_back(y, z), e[y].emplace_back(x, z);

    auto build = [e, &g, &dn, &dfn, &f, &dis](auto &&self, int x, int fa) -> void {
        f[0][dfn[x] = ++dn] = fa;
        for (auto [y, w]: e[x]) {
            if (y == fa) continue;
            g[x].emplace_back(y, w), dis[y] = dis[x] + w;
            self(self, y, x);
        }
    };

    dis[1] = 0;
    build(build, 1, 0);
    vector<bool> vis(n + 1, false);
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (auto [y, w]: g[x]) {
            if (vis[y] or dist[y] <= dist[x] + w) continue;
            dist[y] = dist[x] + w, que.push(y);
        }
    }
    auto get = [dfn](int x, int y) {
        if (dfn[x] < dfn[y]) return x;
        return y;
    };

    for (int i = 1; i <= logN; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            f[i][j] = get(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);

    auto lca = [dfn, get, f](int u, int v) {
        if (u == v) return u;
        u = dfn[u], v = dfn[v];
        if (u > v) swap(u, v);
        int d = log2(v - u++);
        return get(f[d][u], f[d][v - (1 << d) + 1]);
    };

    for (int k, l, r, res; q; q--) {
        cin >> k;
        vector<int> a(k);
        for (auto &i: a) cin >> i;
        l = 0, r = inf, res = -1;
        for (int mid, t, flag; l <= r;) {
            mid = (l + r) >> 1, t = -1, flag = 1;
            for (auto i: a) {
                if (dist[i] <= mid) continue;
                if (t == -1) t = i;
                else t = lca(t, i);
            }
            for (auto i: a) {
                if (min(dist[i], dis[i] - dis[t]) <= mid) continue;
                flag = 0;
                break;
            }
            if (flag) res = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << res << "\n";
    }


}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

这程序好像有点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: 1309ms
memory: 58360kb

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