QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460649#7103. Red Black TreeShayan86TL 1ms5780kbC++234.8kb2024-07-01 23:37:372024-07-01 23:37:38

Judging History

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

  • [2024-07-01 23:37:38]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:5780kb
  • [2024-07-01 23:37:37]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define SZ(x)       (int)x.size()
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

#define lid (id*2)
#define rid (id*2+1)
#define mid ((l+r)/2)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll L = 20;
const ll N = 1e5 + 50;
const ll inf = 1e18;

ll n, m, q, red[N], h[N], dist[N], st[N], ft[N], timer, anc[N], par[N][L];

vector<pii> adj[N];

void dfs(int v, int p = 0){
    if(red[v]) anc[v] = v;
    else anc[v] = anc[p];

    par[v][0] = p;
    for(int i = 1; i < L; i++){
        par[v][i] = par[par[v][i-1]][i-1];
    }

    st[v] = timer++;
    for(auto [u, w]: adj[v]){
        if(u == p) continue;
        h[u] = h[v] + w;
        dist[u] = dist[v] + 1;
        dfs(u, v);
    }
    ft[v] = timer;
}

int getPar(int v, int k){
    for(int i = 0; i < L; i++) if(k >> i & 1) v = par[v][i];
    return v;
}

int lca(int u, int v){
    if(dist[u] > dist[v]) swap(u, v);
    v = getPar(v, dist[v] - dist[u]);
    if(u == v) return v;

    for(int i = L-1; i >= 0; i--){
        if(par[v][i] != par[u][i]){
            v = par[v][i]; u = par[u][i];
        }
    }
    return par[v][0];
}

vector<pll> g[N];
vector<int> child[N];

ll seg[3][N*4], res;

void upd(int i, int x, ll y, int l = 0, int r = n, int id = 1){
    if(l+1 == r){
        seg[i][id] = y; return;
    }
    if(x < mid) upd(i, x, y, l, mid, lid);
    else upd(i, x, y, mid, r, rid);
    seg[i][id] = max(seg[i][lid], seg[i][rid]);
}

ll get(int i, int ql, int qr, int l = 0, int r = n, int id = 1){
    if(ql <= l && r <= qr) return seg[i][id];
    if(qr <= l || r <= ql) return -inf;
    return max(get(i, ql, qr, l, mid, lid), get(i, ql, qr, mid, r, rid));
}

void calc(int v){
    for(int u: child[v]){
        upd(1, st[u], h[u]); 
        upd(2, st[u], -inf);
    }
    ll th = max(max(get(2, st[v], ft[v]), get(1, st[v], ft[v]) - h[v]), max(get(0, 0, st[v]), get(0, ft[v], n)));
    //cout << v << sep << th << sep << get(2, st[v], ft[v]) << sep << get(1, st[v], ft[v]) - h[v] << sep << get(0, 0, st[v]) << sep << get(0, ft[v], n) << endl;
    res = min(res, th);

    for(auto [u, w]: g[v]) calc(u);
    for(int u: child[v]){
        upd(1, st[u], -inf); 
        upd(2, st[u], h[u] - h[anc[u]]);
    }
}

void Main(){
    cin >> n >> m >> q;

    for(int i = 1; i <= m; i++){
        int x; cin >> x; red[x] = 1;
    }

    for(int i = 1; i < n; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }

    timer = 0; dfs(1);

    for(int i = 0; i < 3; i++) for(int j = 0; j < n; j++) upd(i, j, -inf);

    for(int i = 1; i <= q; i++){
        int k;
        cin >> k;

        vector<int> vec, imp;
        for(int j = 1; j <= k; j++){
            int x; cin >> x; 
            imp.pb(x);
            vec.pb(x); vec.pb(anc[x]); 
            child[anc[x]].pb(x);
        }

        sort(all(vec), [&](int i, int j){return st[i] < st[j];});

        vector<int> vc;
        for(int j = 0; j < SZ(vec) - 1; j++){
            vc.pb(vec[j]); vc.pb(lca(vec[j], vec[j+1]));
        }
        vc.pb(vec.back());

        sort(all(vc), [&](int i, int j){return st[i] < st[j];});
        vc.resize(unique(all(vc)) - vc.begin());

        vec = vc;

        vector<int> sta;
        while(!vc.empty()){
            int v = vc.back(); vc.pop_back();
            while(!sta.empty() && ft[sta.back()] <= ft[v]){
                g[v].pb({sta.back(), h[v] - h[sta.back()]});
                sta.pop_back();
            }
            sta.pb(v);
        }
        int root = sta.back();

        for(int j: imp){
            upd(0, st[j], h[j] - h[anc[j]]);
            upd(2, st[j], h[j] - h[anc[j]]);
        }

        res = inf; calc(root);

        cout << res << endl;

        for(int j: vec){
            child[j].clear(); g[j].clear();
            upd(0, st[j], -inf);
            upd(2, st[j], -inf);
        }
    }

    for(int i = 1; i <= n; i++){
        adj[i].clear(); red[i] = 0;
    }
}

int main(){
    fast_io;
    
    int T;
    cin >> T;

    while(T--){
        Main();
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Time Limit Exceeded

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: