QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163232#7103. Red Black Treeucup-team1209AC ✓601ms25736kbC++142.2kb2023-09-03 22:33:112023-09-03 22:33:11

Judging History

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

  • [2023-09-03 22:33:11]
  • 评测
  • 测评结果:AC
  • 用时:601ms
  • 内存:25736kb
  • [2023-09-03 22:33:11]
  • 提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ; 
using pi = pair <int, int> ; 
cs int N = 1e5 + 5; 

void cmn(ll &x, ll y) {
    if(x > y) x = y;
}
void cmx(ll &x, ll y) {
    if(x < y) x = y; 
}

int T; 
int n, m, q;
ll d[N];
ll c[N];
bool red[N];
vector <pi> e[N];

int dfn[N], cnt;
int st[20][N]; 

int mn(int x, int y) {
    return dfn[x] < dfn[y] ? x : y;
}

int lca(int x, int y) {
    if(x == y) return x; 
    if(dfn[x] > dfn[y]) swap(x, y);
    int lg = __lg(dfn[y] - dfn[x]);
    return mn(st[lg][dfn[x]], st[lg][dfn[y] - (1 << lg)]);
}

void dfs(int u, int f, int p) {
    st[0][cnt] = f; 
    dfn[u] = ++ cnt; 
    if(red[u]) p = u; 
    c[u] = d[u] - d[p];
    // cout << u << ' ' << f << ' ' << p << endl;
    for(auto [v, w] : e[u])
    if(v != f) {
        d[v] = d[u] + w; 
        dfs(v, u, p);
    }
}

void work() {
    int k; 
    scanf("%d", &k);
    vector <int> a(k);
    for(int &x : a) scanf("%d", &x);
    sort(a.begin(), a.end(), [&](int x, int y) {
        return c[x] > c[y];
    });
    ll ans = 1e18; 
    int pnt = a[0];
    ll mxd = 0; 
    for(int i = 0; i < k; i++) {
        int x = a[i];
        pnt = lca(x, pnt);
        cmx(mxd, d[x]);
        cmn(ans, max(i + 1 < k ? c[a[i + 1]] : 0, mxd - d[pnt])); 
    }
    cout << ans << '\n';
}

void Main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= m; i++) {
        int x; 
        scanf("%d", &x);
        red[x] = 1; 
    }
    for(int i = 1, u, v, w; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        e[u].pb({v, w});
        e[v].pb({u, w});
    }
    dfs(1, 0, 1);
    for(int i = 1; i < 20; i++)
    for(int j = 1; j + (1 << i) - 1 < n; j++)
    st[i][j] = mn(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    
    for(int t = 0; t < q; t++) {
        work();
    }
    for(int i = 0; i <= n; i++) {
        dfn[i] = 0; 
        e[i].clear();
        d[i] = c[i] = 0; 
        red[i] = 0; 
    }
    cnt = 0; 
}

int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> T;
    while(T--) Main();
    return 0; 
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 601ms
memory: 25736kb

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