QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162958#7103. Red Black Treeucup-team061AC ✓820ms38612kbC++202.2kb2023-09-03 18:14:062023-09-03 18:14:07

Judging History

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

  • [2023-09-03 18:14:07]
  • 评测
  • 测评结果:AC
  • 用时:820ms
  • 内存:38612kb
  • [2023-09-03 18:14:06]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define eb emplace_back
#define eps 1e-6
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 2e7 + 10;
int n, m, q;
int r[N];
vector<pair<int, int>> e[N];
int f[N][21], near[N], cost[N], dep[N];
void dfs(int p, int w, int fa){
    if(r[p]) near[p] = p, w = 0;
    cost[p] = w;
    f[p][0] = fa, dep[p] = dep[fa] + 1;
    for(int i = 1; i <= 20; i++) f[p][i] = f[f[p][i - 1]][i - 1];
    for(auto [to, d] : e[p]){
        if(to == fa) continue;
        near[to] = near[p];
        dfs(to, w + d, p);
    }
}
int LCA(int x, int y){
    if(dep[x] < dep[y]) swap(x, y);
    int t = 20;
    while(dep[x] != dep[y]){
        if(dep[f[x][t]] >= dep[y]) x = f[x][t];
        t--;
    }
    t = 20;
    while(x != y){
        while(t && f[x][t] == f[y][t]) t--;
        x = f[x][t], y = f[y][t];
    }
    return x;
}
int x[N];
bool cmp(int a, int b){
    return cost[a] > cost[b];
}
void init(){
    for(int i = 0; i <= n; i++){
        r[i] = 0, near[i] = 0, cost[i] = 0, dep[i] = 0;
        e[i].clear();
        for(int j = 0; j <= 20; j++) f[i][j] = 0;
    }
}
void solve(){
    cin >> n >> m >> q;
    init();
    for(int i = 1, a; i <= m; i++) cin >> a, r[a] = 1;
    for(int i = 1, u, v, w; i < n; i++){
        cin >> u >> v >> w;
        e[u].pb({v, w});
        e[v].pb({u, w});
    }
    dfs(1, 0, 0);
    //for(int i = 1; i <= n; i++) cout << i << ' ' << cost[i] << '\n';
    while(q--){
        int k;
        cin >> k;
        for(int i = 1; i <= k; i++) cin >> x[i];
        x[k + 1] = 0;
        sort(x + 1, x + 1 + k, cmp);
        int ans = cost[x[1]], lca = x[1];
        int mxd = dep[near[x[1]]], oric = cost[x[1]];
        for(int i = 1; i <= k; i++){
            lca = LCA(lca, x[i]);
            mxd = max(mxd, dep[near[x[i]]]);
            if(dep[lca] >= mxd){
                ans = min(ans, max(oric - cost[lca], cost[x[i + 1]]));
            }else break;
        }
        cout << ans << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while(T--) solve();
    return 0;
}

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

詳細信息

Test #1:

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

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: 820ms
memory: 38612kb

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