QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156869#7103. Red Black Treeucup-team859#AC ✓843ms34292kbC++143.4kb2023-09-02 14:30:442023-09-02 14:56:14

Judging History

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

  • [2023-09-02 14:56:14]
  • 评测
  • 测评结果:AC
  • 用时:843ms
  • 内存:34292kb
  • [2023-09-02 14:30:44]
  • 提交

answer

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;

constexpr ll INF = (ll) 1e18;

constexpr int MAXN = (int) 1e5;
constexpr int LOG = 20;

int rmq[LOG + 1][2 * MAXN + 1];
int lg[2 * MAXN + 1];


int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    lg[1] = 0;
    for (int i = 2; i <= 2 * MAXN; i++) {
        lg[i] = lg[i >> 1] + 1;
    }

    int t;
    cin >> t;
    while (t--) {
        int n, m, q;
        cin >> n >> m >> q;

        vector<bool> r(n + 1); 
        for (int i = 1; i <= m; i++) {
            int x;
            cin >> x;
            r[x] = 1;
        }

        vector<vector<pair<int, int>>> g(n + 1);
        for (int i = 1; i < n; i++) {
            int x, y, w;
            cin >> x >> y >> w;
            g[x].push_back({y, w});
            g[y].push_back({x, w});
        }

        vector<int> first(n + 1);
        int size = 0;

        vector<ll> sum(n + 1);
        vector<ll> dist(n + 1);

        function<void(int, int, int)> dfs = [&](int node, int par, int anc) {
            if (r[node]) {
                dist[node] = 0;
            } else {
                if (anc == -1) {
                    dist[node] = INF;
                } else {
                    dist[node] = sum[node] - sum[anc];
                }
            }

            rmq[0][++size] = node;
            first[node] = size;

            for (auto itr : g[node]) {
                if (itr.first != par) {
                    sum[itr.first] = sum[node] + itr.second;
                    dfs(itr.first, node, r[node] ? node : anc);
                    rmq[0][++size] = node;
                }
            }
        };

        dfs(1, 0, -1);

        for (int bit = 1; (1 << bit) <= size; bit++) {
            for(int i = 1; i + (1 << bit) <= size + 1; i++) {
                int a = rmq[bit - 1][i], b = rmq[bit - 1][i + (1 << (bit - 1))];
                rmq[bit][i] = (sum[a] < sum[b] ? a : b);
            }
        }

        auto GetLCA = [&](int x, int y) {
            x = first[x], y = first[y];

            if(x > y) swap(x, y);

            int bit = lg[y - x + 1];
            int a = rmq[bit][x], b = rmq[bit][y - (1 << bit) + 1];
            return (sum[a] < sum[b] ? a : b);
        };

        while (q--) {
            int k;
            cin >> k;

            vector<int> nodes(k);
            for (auto& node : nodes) {
                cin >> node;
            }

            auto Check = [&](ll D) {
                int lca = -1;
                for (auto node : nodes) {
                    if (dist[node] <= D) continue;
                    
                    lca = (lca == -1 ? node : GetLCA(lca, node));
                }


                for (auto node : nodes) {
                    if (dist[node] > D && sum[node] - sum[lca] > D) {
                        return false;
                    }
                }
                return true;
            };

            ll result = -1;
            for (ll step = 1LL << 50; step; step >>= 1) {
                if (Check(result + step) == false) {
                    result += step;
                }
            }
            cout << result + 1 << "\n";
        }
    }
    

    return 0;
}

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

详细

Test #1:

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

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: 843ms
memory: 34292kb

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