QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181013#7103. Red Black Treeucup-team1069#TL 2ms26388kbC++203.8kb2023-09-16 15:05:482023-09-16 15:05:48

Judging History

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

  • [2023-09-16 15:05:48]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:26388kb
  • [2023-09-16 15:05:48]
  • 提交

answer

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

const int N = 3e5 + 123;
const int LOG = 20;
using ll = long long;

vector<pair<int,int>>g[N];
int tinLCA[N], toutLCA[N];
int red[N];
int sum[N];
int timer;
int up[N][LOG];

void dfsLCA(int v, int p) {
    tinLCA[v] = ++timer;
    up[v][0] = p;
    for (int i = 1 ; i < LOG ; ++ i) up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto [to, w] : g[v]) if (to != p) {
        dfsLCA(to, v);
    }
    toutLCA[v] = ++timer;
}

ll t[N << 2];

void upd(int pos, ll val, int l = 0, int r = N, int v = 1) {
    if (r - l == 1) {
        t[v] = val;
        return;
    }
    int m = (l + r) >> 1;
    if (pos < m) upd(pos, val, l, m, v << 1);
    else upd(pos, val, m, r, v<<1|1);
    t[v] = max(t[v << 1], t[v<<1|1]);
}

ll get(int L, int R, int l = 0, int r = N, int v = 1) {
    if (L <= l && r <= R) return t[v];
    if (r <= L || R <= l) return 0;
    int m = (l + r) >> 1;
    return max(get(L, R, l, m, v << 1), get(L, R, m, r, v<<1|1));
}

int upper(int a, int b) {
    return tinLCA[a] <= tinLCA[b] && toutLCA[a] >= toutLCA[b];
}

int lca(int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = LOG - 1 ; i >= 0 ; -- i) {
        if (!upper(up[a][i], b)) a = up[a][i];
    }
    return up[a][0];
}

using ll = long long;

const ll INF = 1e18 + 123;

int tin[N], tout[N];

vector<int>pot;

int k[N];

void dfs(int v, int p) {
    tin[v] = timer++;
    for (auto [to, w] : g[v]) if (to != p) {
        if (to == up[v][0]) continue;
        if (red[to]) continue;
        sum[to] = sum[v] + w;
        dfs(to, v);
    }
    tout[v] = timer;
}

bool cmpLCA(int i, int j) {
    return tinLCA[i] < tinLCA[j];
}

bool cmp(int i, int j) {
    return tin[i] < tin[j];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int test;
    cin >> test;
    while (test--) {
        int n, m, q;
        cin >> n >> m >> q;
        timer = 0;
        for (int i = 1 ; i <= n ; ++ i) {
            tin[i] = 0, tout[i] = 0;
            tinLCA[i] = 0, toutLCA[i] = 0;
            g[i].clear();
            red[i] = 0;
            sum[i] = 0;
        }
        for (int i = 1 ; i <= m ; ++ i) {
            int x;
            cin >> x;
            red[x] = 1;
        }
        for (int i = 1 ; i <= n - 1 ; ++ i) {
            int a, b, c;
            cin >> a >> b >> c;
            g[a].emplace_back(b, c);
            g[b].emplace_back(a, c);
        }
        dfsLCA(1, 1);
        timer = 0;
        for (int i = 1 ; i <= n ; ++ i) {
            if (red[i] == 1) {
                sum[i] = 0;
                dfs(i, i);
            }
        }
        while (q--) {
            int sz;
            cin >> sz;
            ll before = 0;
            for (int i = 1 ; i <= sz ; ++ i) {
                cin >> k[i];
                before += sum[k[i]];
            }
            sort(k + 1, k + 1 + sz, cmpLCA);
            pot.clear();
            for (int i = 1 ; i <= sz ; ++ i) {
                pot.emplace_back(k[i]);
                int j = (i == sz ? 1 : i + 1);
                pot.emplace_back(lca(k[i], k[j]));
            }
            sort(k + 1, k + 1 + sz, cmp);
            ll ans = before;
            for (int i = 1 ; i <= sz ; ++ i) {
                upd(tin[k[i]], sum[k[i]]);
            }
            for (int v : pot) {
                int l = tin[v], r = tout[v];
                ll x1 = get(0, l);
                ll x2 = get(l, r) - sum[v];
                ll x3 = get(r, N);
                ans = min(ans, max(x1,max(x2,x3)));
            }
            for (int i = 1 ; i <= sz ; ++ i) {
                upd(tin[k[i]], 0);
            }
            cout << ans << "\n";
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: