QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181278#7103. Red Black Treeucup-team1069#AC ✓1395ms46620kbC++203.9kb2023-09-16 17:18:532023-09-16 17:18:53

Judging History

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

  • [2023-09-16 17:18:53]
  • 评测
  • 测评结果:AC
  • 用时:1395ms
  • 内存:46620kb
  • [2023-09-16 17:18:53]
  • 提交

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];
ll 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;
}

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];
}

ll p[N];
ll pref[N], suf[N];

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];
            }
            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);
            vector<int> pos;
            ll mx = -INF;
            pos.push_back(0);
            for (int i = 1; i <= sz; i++) {
                mx = max(mx, sum[k[i]]);
                pos.push_back(tin[k[i]]);
            }
            pos.push_back(n + 1);
            p[0] = 0;
            for (int i = 1; i <= sz; i++) {
                p[i] = (mx == sum[k[i]]);
                p[i] += p[i - 1];
            }
            ll ans = mx;
            suf[sz + 1] = 0;
            for (int i = sz; i >= 1; i--) {
                suf[i] = max(suf[i + 1], sum[k[i]]);
            }
            pref[0] = 0;
            for (int i = 1; i <= sz; i++) {
                pref[i] = max(pref[i - 1], sum[k[i]]);
            }
            for (int v : pot) {
                int l = lower_bound(pos.begin(), pos.end(), tin[v]) - pos.begin();
                int r = upper_bound(pos.begin(), pos.end(), tout[v]) - pos.begin() - 1;
                if (l > r) continue;
                if (p[l - 1] + (p[sz] - p[r]) == 0) 
                    ans = min(ans, max({pref[l - 1], suf[r + 1], mx - sum[v]}));
            }
            cout << ans << "\n";
        }
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1395ms
memory: 46620kb

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