QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#158994#7103. Red Black Treeucup-team228#AC ✓836ms36380kbC++205.2kb2023-09-02 17:18:332023-09-02 17:18:35

Judging History

This is the latest submission verdict.

  • [2023-09-02 17:18:35]
  • Judged
  • Verdict: AC
  • Time: 836ms
  • Memory: 36380kb
  • [2023-09-02 17:18:33]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

/*
 * TOUR SIZE IS TWO TIMES MORE THAN N, SO UPDATE SPARSE_TABLE::N CORRESPONDINGLY
 *
 * checked on this problem: https://codeforces.com/problemset/problem/342/E
 */

enum TableType { VAL, ARG };

template <typename T, TableType S = TableType::VAL, typename Cmp = less<T>>
struct sparse_table{
    // VAL returns value, ARG returns position of value
    // less<> for minimum, greater<> for maximum
    // d[i][j] = min(a[i], a[i + 1], ... , a[i + (1 << j) - 1])
    // get(l, r) = min(a[l], a[l + 1], ... , a[r])
    static const int N = 2e5 + 10;
    static const int L = 19;
    T a[N];
    int d[N][L], rem[N];
    void build(int n, Cmp cmp = {}) {
        for (int i = 1; i <= n; i++) { d[i][0] = i; }
        for (int j = 1; j <= L - 1; j++) {
            for (int i = 1; i <= n; i++) {
                if (i + (1 << j) - 1 > n) { continue; }
                d[i][j] = cmp(a[d[i][j - 1]], a[d[i + (1 << (j - 1))][j - 1]]) ? d[i][j - 1] : d[i + (1 << (j - 1))][j - 1];
            }
        }
        for (int i = 1; i <= n; i++) { rem[i] = log2(i); }
    }
    T get(int l, int r, Cmp cmp = {}) {
        int lg = rem[r - l + 1];
        int pos = cmp(a[d[l][lg]], a[d[r - (1 << lg) + 1][lg]]) ? d[l][lg] : d[r - (1 << lg) + 1][lg];
        if constexpr (S == TableType::VAL) { return a[pos]; } else { return pos; }
    }
};

sparse_table<int, TableType::ARG> table;

const ll inf = 1e18;
const int N = 1e5 + 10;
int depth[N], in[N], out[N];
vector<pair<int, int>> g[N];
vector<int> tour;

bool is_red[N];
int up[N];
ll mem[N];

void init(int n) {
    for (int i = 1; i <= n; i++) {
        depth[i] = 0;
        in[i] = 0;
        out[i] = 0;
        g[i].clear();
        is_red[i] = false;
        up[i] = 0;
        mem[i] = 0;
    }
    tour.clear();
}

void dfs_lca(int v = 1, int p = 1) {
    in[v] = tour.size();
    tour.push_back(v);
    for (auto [to, w] : g[v]) {
        if (to != p) {
            depth[to] = depth[v] + 1;
            dfs_lca(to, v);
            tour.push_back(v);
        }
    }
    out[v] = tour.size() - 1;
}

int lca(int u, int v) {
    if (out[u] > out[v]) {
        swap(u, v);
    }
    return tour[table.get(in[u] + 1, out[v] + 1) - 1];
}

void precalc_lca() {
    dfs_lca();
    for (int i = 1; i <= tour.size(); i++) {
        table.a[i] = depth[tour[i - 1]];
    }
    table.build(tour.size());
}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

void dfs_up(int v = 1, int p = 1) {
    if (is_red[v]) {
        up[v] = v;
        mem[v] = 0;
    }
    for (auto [to, w] : g[v]) {
        if (to != p) {
            up[to] = up[v];
            mem[to] = mem[v] + w;
            dfs_up(to, v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int t;
    cin >> t;
    while (t--) {
        int n, m, q;
        cin >> n >> m >> q;
        init(n);
        for (int i = 1; i <= m; i++) {
            int x;
            cin >> x;
            is_red[x] = true;
        }
        for (int i = 1; i <= n - 1; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }

        precalc_lca();
        dfs_up();

        while (q--) {
            int k;
            cin >> k;
            vector<int> a(k);
            for (int& v : a) {
                cin >> v;
            }
            vector<pair<ll, int>> b;
            b.reserve(k);
            for (int v : a) {
                b.emplace_back(mem[v], v);
            }
            sort(b.begin(), b.end());

            if (b.back().first == 0) {
                cout << "0\n";
            } else {
                int x = b.back().second;
                vector<tuple<int, int, ll>> c;
                c.reserve(k);
                ll other = 0;
                for (int v : a) {
                    int l = lca(x, v);
                    if (depth[l] <= depth[up[x]] || depth[l] <= depth[up[v]]) {
                        other = max(other, mem[v]);
                    } else {
                        c.emplace_back(depth[l], l, mem[v]);
                    }
                }
                sort(c.begin(), c.end());

                vector<ll> pref(c.size());
                pref[0] = get<2>(c.front());
                for (int i = 1; i < c.size(); i++) {
                    pref[i] = max(pref[i - 1], get<2>(c[i]));
                }
                vector<ll> suf(c.size());
                suf[c.size() - 1] = get<2>(c.back());
                for (int i = int(c.size()) - 2; i >= 0; i--) {
                    suf[i] = max(suf[i + 1], get<2>(c[i]));
                }

                ll ans = inf;
                for (int i = 0; i < c.size(); i++) {
                    ans = min(ans, max({other, i == 0 ? 0 : pref[i - 1], suf[i] - mem[get<1>(c[i])]}));
                }
                cout << ans << "\n";
            }
        }
    }

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 836ms
memory: 36380kb

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