QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162591#7103. Red Black TreeGenshinImpactsFault#AC ✓1076ms35928kbC++173.0kb2023-09-03 14:47:532023-09-03 14:47:54

Judging History

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

  • [2023-09-03 14:47:54]
  • 评测
  • 测评结果:AC
  • 用时:1076ms
  • 内存:35928kb
  • [2023-09-03 14:47:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define M 200010
#define LL long long
int Red[M];
vector<pair<int, int>> G[M];
int dfn[M], dfs_clock;
int ft[20][M];
LL h[M];
pair<int, int> lca1[M]; int tot;
int dep[M];
LL cost[M];
void dfs(int x, int fa) {
    dfn[x] = ++ dfs_clock;
    ft[0][x] = fa;
    dep[x] = dep[fa] + 1;
    for(int i = 1; i <= 17; ++ i) {
        ft[i][x] = ft[i - 1][ft[i - 1][x]];
    }
    for(auto [v, w] : G[x]) {
        if(v == fa) continue;
        h[v] = h[x] + w;
        dfs(v, x);
    }
}
int lca(int x, int y) {
    if(dep[x] < dep[y]) swap(x, y);
    int t = dep[x] - dep[y];
    for(int i = 0; i <= 17; ++ i) {
        if((t >> i) & 1) {
            x = ft[i][x];
        }
    }
    if(x == y) return x;
    for(int i = 17; i >= 0; -- i) {
        if(ft[i][x] != ft[i][y]) {
            x = ft[i][x], y = ft[i][y];
        }
    }
    return ft[0][x];
}
void dfs1(int x, int fa, int p) {
    cost[x] = h[x] - h[p];
    for(auto [v, w] : G[x]) {
        if(v == fa) continue;
        dfs1(v, x, (Red[v] ? v : p));
    }
}
int V[M];
bool check(int k, LL lim) {
    int L = -1, R = -1, mnpos = -1;
    LL mx = 0;
    for(int i = 1; i <= k; ++ i) {
        if(cost[V[i]] > lim) {
            mx = max(mx, h[V[i]]);
            if(L == -1) L = i;
            R = i;
            if(mnpos == -1) mnpos = i;
            else {
                if(cost[V[i]] < cost[V[mnpos]]) {
                    mnpos = i;
                }
            }
        }
    }
    if(L == -1) return 1;
    int LCA;
    if(lca1[mnpos].first == tot) {
        LCA = lca1[mnpos].second;
    }
    else {
        LCA = lca(V[L], V[R]);
        lca1[mnpos] = {tot, LCA};
    }
    if(mx - h[LCA] <= lim) return 1;
    return 0;
}
void solve() {
    ++ tot;
    int k;
    cin >> k;
    for(int i = 1; i <= k; ++ i) {
        cin >> V[i];
    }
    sort(V + 1, V + k + 1, [](int x, int y){
        return dfn[x] < dfn[y];
    });
    LL l = 0, r = 1e15, t = 0;
    while(l <= r) {
        LL mid = l + r >> 1;
        if(check(k, mid)) r = (t = mid) - 1;
        else l = mid + 1; 
    }
    cout << t << "\n";
}
void Do() {
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++ i) {
        Red[i] = 0;
    }
    for(int i = 1; i <= m; ++ i) {
        int x;
        cin >> x;
        Red[x] = 1;
    }
    for(int i = 1; i <= n; ++ i) {
        G[i].clear();
    }
    for(int i = 1; i < n; ++ i) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dfs_clock = 0;
    dfs(1, 0);
    dfs1(1, 0, 1);
    while(q --) {
        solve();
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T --) {
        Do();
    }
}
/*
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

*/

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

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 24608kb

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: 1076ms
memory: 35928kb

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