QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#195461#7103. Red Black TreeeleusWA 1078ms26572kbC++234.3kb2023-10-01 04:34:062023-10-01 04:34:07

Judging History

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

  • [2023-10-01 04:34:07]
  • 评测
  • 测评结果:WA
  • 用时:1078ms
  • 内存:26572kb
  • [2023-10-01 04:34:06]
  • 提交

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

const int N = 1e5;

int read()
{
    int t;
    scanf("%d", &t);
    return t;
}

void testcase()
{
    int n = read(), m = read(), q = read();

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

    for (int i = 1; i <= m; i++) {
        int h = read();
        red[h] = 1;
    }

    for (int i = 1; i < n; i++) {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        g[u].pb({v, w});
        g[v].pb({u, w});
    }

    vector<long long> cost(n + 1), weight(n + 1);
    vector<int> depth(n + 1);
    vector<int> vis(n + 1);
    int LG = __lg(n) + 2;
    vector<vector<int>> up(n + 1, vector<int>(LG));

    queue<pii> bfs;
    bfs.push({1, 0});
    up[1][0] = 1;
    vis[1]++;

    while (bfs.size()) {
        auto [u, near] = bfs.front();
        bfs.pop();

        for (auto [v, w] : g[u]) {
            if (vis[v]) continue;
            vis[v]++;
            up[v][0] = u;
            weight[v] = weight[u] + w;
            depth[v] = depth[u] + 1;
            if (red[v]) {
                cost[v] = 0;
                bfs.push({v, 0});
            }
            else {
                cost[v] = near + w;
                bfs.push({v, cost[v]});
            }
        }
    }

    for (int j = 1; j < LG; j++) {
        for (int i = 1; i <= n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    auto LCA = [&] (int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        int dif = depth[v] - depth[u];
        for (int i = LG - 1; i >= 0; i--) {
            if (Checkbit(dif, i)) {
                v = up[v][i];
            }
        }
        if (v == u) return u;
        for (int i = LG - 1; i >= 0; i--) {
            if (up[v][i] != up[u][i]) {
                v = up[v][i];
                u = up[u][i];
            }
        }
        return up[u][0];
    };

    for (int _ = 0; _ < q; _++) {   
        int k;
        k = read();

        vector<int> nodes(k);
        vector<pair<long long,int>> a;
        for (int i = 0; i < k; i++) {
            nodes[i] = read();
            a.pb({cost[nodes[i]], nodes[i]});
        }

        sort(rall(a));
        long long ans = 1e18;
        long long d = 0;
        // debug(a);
        int lca = a[0].s;
        for (int i = 0; i < k; i++) {
            d = max(weight[a[i].s], d);
            lca = LCA(lca, a[i].s);
            long long tmp = d - weight[lca];
            if(i + 1 < k) {
                tmp = max(tmp, a[i + 1].f);
            }
            ans = min(ans, tmp);
        }
        // cout << ans << "\n";
        printf("%lld\n", ans);
    }
}

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

詳細信息

Test #1:

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

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: 1078ms
memory: 26572kb

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 59th lines differ - expected: '2307445864', found: '2021596206'