QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#195434#7103. Red Black TreeeleusWA 1276ms54120kbC++145.1kb2023-10-01 04:21:252023-10-01 04:21:26

Judging History

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

  • [2023-10-01 04:21:26]
  • 评测
  • 测评结果:WA
  • 用时:1276ms
  • 内存:54120kb
  • [2023-10-01 04:21:25]
  • 提交

answer

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template <class K,class V> using omap = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long 
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define lb lower_bound
#define ub upper_bound
#define Checkbit(a,i) (((a)>>(i))&1)
#define Setbit(a,i) ((a)^=1LL<<(i))

int mod = 1e9 + 7;
class LCA 
{
public:
    vector<int> depth;
    vector<int> wdist;
    vector<vector<pair<int,int>>> graph;
    vector<int> sub;
    vector<vector<int>> up;
    int N;
    int LOG;
    LCA(int n) : N(n) {
        depth.assign(N + 5, 0);
        graph.assign(N + 5, vector<pair<int,int>>());
        sub.assign(N + 5, 0);
        wdist.assign(N + 5, 0);
        LOG = __lg(N) + 2;
        up.assign(N + 5, vector<int>(LOG));
    }
    void addEdge(int u, int v, int w = 1) {
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }
    void dfs(int u, int p = 0, int cost = 0) {
        sub[u] = 1;
        up[u][0] = p;
        depth[u] = depth[p] + 1;
        wdist[u] = cost;
        for (int i = 1; i < LOG; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
        }
        for (auto [v, w] : graph[u]) {
            if (v != p) {
                dfs(v, u, cost + w);
                sub[u] += sub[v];
            }
        }
    }
    int lca(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        int dif = depth[v] - depth[u];
        for (int i = LOG - 1; i >= 0; i--) {
            if ((dif >> i) & 1) {
                v = up[v][i];
            }
        }
        if (u == v) return u;
        for (int i = LOG - 1; i >= 0; i--) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
    int distance(int u, int v)
    {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
    int kth(int u, int k)
    {
        for (int i = LOG - 1; i >= 0; i--) {
            if ((k >> i) & 1) {
                u = up[u][i];
            }
        }
        return u;
    }
};
const int N = 1e5;

void testcase()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<pair<int,int>>> g(n + 1);
    vector<int> red(n + 1);

    for (int i = 1; i <= m; i++) {
        int h;
        cin >> h;
        red[h] = 1;
    }
    LCA t(n);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin>> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
        t.addEdge(u, v);
    }

    t.dfs(1);

    vector<int> cost(n + 1), weight(n + 1);
    vector<int> near(n + 1);

    function<void(int,int,int,int)> dfs = [&] (int u, int p, int nearest, int r) {
        if (!red[u]) {
            cost[u] = nearest;
            near[u] = r;
        }
        else {
            r = u;
            nearest = 0;
            weight[u] = 0;
        }
    
        for (auto [v, w] : g[u]) {
            if (v ^ p) {
                weight[v] = weight[u] + w;
                dfs(v, u, nearest + w, r);
            }
        }
    };

    dfs(1, 0, 0, 0);

    for (int _ = 0; _ < q; _++) {   
        int k;
        cin >> k;
        vector<int> nodes(k);
        vector<pii> a;
        for (int i = 0; i < k; i++) {
            cin >> nodes[i];
            a.pb({cost[nodes[i]], nodes[i]});
        }
        sort(rall(a));
        int ans = 1e18;
        int d = 0;
        int lca = a[0].s;
        for (int i = 0; i < k; i++) {
            d = max(weight[a[i].s], d);
            lca = t.lca(lca, a[i].s);
            int tmp = d - weight[lca];
            // debug(lca, d);
            if(i + 1 < k) {
                tmp = max(tmp, a[i + 1].f);
            }
            ans = min(ans, tmp);
        }
        cout << ans << "\n";
    }
}

signed main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    cin >> t;
    int cs = 1;
    while (t--) {
        //cout << "Case " << cs++ << ":" << " ";
        testcase();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Wrong Answer
time: 1276ms
memory: 54120kb

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:

wrong answer 691st lines differ - expected: '549790714', found: '374667774'