QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#158759#7103. Red Black Treeucup-team1600#AC ✓949ms52344kbC++145.9kb2023-09-02 16:58:132023-09-02 16:58:14

Judging History

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

  • [2023-09-02 16:58:14]
  • 评测
  • 测评结果:AC
  • 用时:949ms
  • 内存:52344kb
  • [2023-09-02 16:58:13]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = 1e5 + 11, inf = 1000111222;

vector <pii> edge[max_n];
int a[max_n] = {};

vector <int> euler;

int tin[max_n] = {}, h[max_n] = {}, tout[max_n] = {}, need[max_n] = {};
ll dist[max_n] = {};

inline void dfs (int v, int p = -1) {
    if (a[v]) {
        dist[v] = 0;
        need[v] = v;
    }
    tin[v] = len(euler);
    euler.pb(v);
    for (auto &ed : edge[v]) {
        int to, len;
        tie(to, len) = ed;
        if (to == p) {
            continue;
        }
        h[to] = h[v] + 1;
        need[to] = need[v];
        dist[to] = dist[v] + len;
        dfs(to, v);
        euler.pb(v);
    }
    tout[v] = len(euler);
}


struct node {
public:
    int val;
    node (int x = -1) : val(x) {}
};

inline node comb (node a, node b) {
    if (h[a.val] < h[b.val]) {
        return a;
    }
    return b;
}

struct RMQ {
    /// init O(n*logn) time and memory
    /// query O(1)
public:
    int n, k;
    vector <vector <node> > up;
    vector <int> f;
    vector <int> a;

    RMQ() {}

    RMQ (int n, vector <int> a) : n(n), a(a) {
        k = 0;
        while ((1 << k) <= n) {
            ++k;
        }
        init();
    }

    inline void init () {
        up.assign(k, vector <node> (n));
        for (int st = 0; st < k; st++) {
            int len = 1 << st;
            for (int c = len; c < n + len; c += len * 2) {
                if (c < n) {
                    up[st][c] = node(a[c]);
                }
                if (c - 1 < n) {
                    up[st][c - 1] = node(a[c - 1]);
                }
                for (int i = c + 1; i < c + len; i++) {
                    if (i >= n) break;
                    up[st][i] = comb(up[st][i - 1], node(a[i]));
                }
                for (int i = c - 2; i >= c - len; i--) {
                    if (i >= n) continue;
                    if (i + 1 < n) {
                        up[st][i] = comb(node(a[i]), up[st][i + 1]);
                    }
                    else {
                        up[st][i] = node(a[i]);
                    }
                }
            }
        }
        f.resize(n + n);
        for (int i = 2; i < n + n; i++) {
            f[i] = f[i / 2] + 1;
        }
    }

    node query (int l, int r) {
        if (l == r) return node(a[r]);
        int t = f[l ^ r];
        return comb(up[t][l], up[t][r]);
    };

};
RMQ t;

inline int lca (int a, int b) {
    int l = tin[a];
    int r = tin[b];
    if (l > r) swap(l, r);
    return t.query(l, r).val;
}


inline void test_case () {
    int n, m, q;
    cin >> n >> m >> q;
    euler.clear();
    for (int i = 0; i < n; i++) {
        edge[i].clear();
        a[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        int r;
        cin >> r;
        --r;
        a[r] = 1;
    }
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        --u, --v;
        edge[u].pb({v, w});
        edge[v].pb({u, w});
    }
    dfs(0);
    t = RMQ(len(euler), euler);
    for (int i = 0, k; i < q; i++) {
        cin >> k;
        vector <int> ver(k);
        for (auto &j : ver) {
            cin >> j;
            --j;
        }
        ll l = 0, r = 1e14;
        while (l < r) {
            ll mid = (l + r) / 2ll;
            int v = -1;
            for (auto &j : ver) {
                if (dist[j] > mid) {
                    if (v == -1) {
                        v = j;
                    }
                    else {
                        v = lca(v, j);
                    }
                }
            }
            bool ok = true;
            for (auto &j : ver) {
                if (dist[j] > mid) {
                    if (need[j] != need[v] || dist[j] - dist[v] > mid) {
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        cout << r << '\n';
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    for (int test = 1; test <= t; test++) {
        test_case();
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 949ms
memory: 52344kb

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