QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498201#9165. Petrol stationsQwerty12320 0ms3568kbC++238.9kb2024-07-30 04:31:172024-07-30 04:31:17

Judging History

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

  • [2024-07-30 04:31:17]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3568kb
  • [2024-07-30 04:31:17]
  • 提交

answer

#include <bits/stdc++.h>

// #define int int64_t
int K;

struct Shit {
    int64_t tm;
    int cnt, prf;

    bool operator<(const Shit& other) const {
        return tm < other.tm;
    }
};
struct Cum {
    int64_t dlt;
    int sh;
    std::vector<Shit> vec;

    bool operator<(const Cum& other) const {
        return false;
    }
};
using Fuck = std::vector<Cum>;
// using Fuck2 = std::pair<int64_t, Fuck>;

int cum_size(const Cum& c) {
    return c.vec.size() - c.sh;
}

void cum_push(Cum& a) {
    for (int i = a.sh; i < a.vec.size(); i++) {
        a.vec[i].tm += a.dlt;
    }
}

Cum cum_merge(Cum& a, Cum& b) {
    Cum res(0, 0, {});
    cum_push(a);
    cum_push(b);
    res.vec.resize(cum_size(a) + cum_size(b));
    std::merge(a.vec.begin() + a.sh, a.vec.end(),
               b.vec.begin() + b.sh, b.vec.end(),
               res.vec.begin());
    for (int i = 0, s = 0; i < res.vec.size(); i++) {
        res.vec[i].prf = (s += res.vec[i].cnt);
    }

    a.dlt = 0, a.sh = 0, a.vec.clear();
    b.dlt = 0, b.sh = 0, b.vec.clear();
    return res;
}

// merges to a
void fuck_merge(Fuck& a, Fuck& b) {
    a.resize(std::max(a.size(), b.size()) + 1);
    Cum carry{0, 0, {}};
    for (int i = 0; i < a.size(); i++) {
        if (cum_size(carry)) {
            if (cum_size(a[i])) {
                carry = cum_merge(carry, a[i]);
            } else {
                a[i] = std::move(carry);
            }
        }
        if (i < b.size() && cum_size(b[i])) {
            if (cum_size(a[i])) {
                carry = cum_merge(a[i], b[i]);
            } else {
                a[i] = std::move(b[i]);
            }
        }
    }
    assert(cum_size(carry) == 0);
    while (a.size() && cum_size(a.back()) == 0) {
        a.pop_back();
    }
    b.clear();
}

__attribute__((optimize("O3"), target("avx2"))) std::pair<int, int> cum_fisting(Cum& c, int w) {
    c.dlt -= w;
    int dlt = 0;
    int sum = 0;
    int it = std::lower_bound(c.vec.begin() + c.sh, c.vec.end(), Shit{-c.dlt}) - c.vec.begin();
    // while (cum_size(c) && c.vec[c.sh].tm + c.dlt < 0) {

    sum = c.vec[it - 1].prf - (c.sh == 0 ? 0 : c.vec[c.sh - 1].prf);
    // for (int i = c.sh; i < it; i++) {
    //     sum += c.vec[i].cnt;
    // }
    dlt = it - c.sh;
    c.sh = it;
    if (dlt) {
        c.vec.push_back({(K - w) - c.dlt, sum});
        c.vec.back().prf = c.vec.back().cnt + (c.vec.size() == 1 ? 0 : c.vec.rbegin()[1].prf);
    }
    return {dlt, sum};
}

int fuck_fisting(Fuck& f, int w) {
    int sum = 0;
    for (auto& cum : f) {
        auto [dt, sm] = cum_fisting(cum, w);
        sum += sm;
    }
    return sum;
}

void cum_reverse_fisting(Cum& c, int w, int ftg) {
    c.dlt += w;
    if (ftg) {
        c.sh -= ftg;
        c.vec.pop_back();
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n >> K;
    std::vector<std::vector<std::pair<int, int>>> gr(n);
    std::vector<std::vector<int64_t>> dp(n);

    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        gr[u].push_back({v, w}), gr[v].push_back({u, w});
    }
    for (int i = 0; i < n; i++) {
        dp[i].resize(gr[i].size());
    }
    std::vector<int> fising_sz(n), fisting_depth(n);
    {
        auto dfs = [&](auto dfs, int v, int f) -> void {
            fising_sz[v] = 1;
            for (auto [t, w] : gr[v]) {
                if (t != f) {
                    fisting_depth[t] = fisting_depth[v] + 1;
                    dfs(dfs, t, v);
                    fising_sz[v] += fising_sz[t];
                }
            }
        };
        dfs(dfs, 0, -1);
    }

    auto get_sb_sz = [&](int u, int v) {
        if (fisting_depth[u] < fisting_depth[v]) {
            return fising_sz[v];
        }
        return n - fising_sz[u];
    };

    // for (int i = 0; i < n; i++) {
    //     auto dfs = [&](auto dfs, int v, int fr) -> Fuck {
    //         Fuck f;
    //         f.push_back(Cum{0, 0, {Shit{K, 1}}});
    //         for (int ti = 0; ti < gr[v].size(); ti++) {
    //             auto [t, w] = gr[v][ti];
    //             if (t == fr) {
    //                 continue;
    //             }
    //             auto f2 = dfs(dfs, t, v);
    //             int sum = fuck_fisting(f2, w);
    //             dp[v][ti] = sum;
    //             fuck_merge(f, f2);
    //         }
    //         return f;
    //     };
    //     dfs(dfs, i, -1);
    // }

    std::vector<int> sz(n), used(n, 0);

    auto find = [&](int v) {
        auto dfs = [&](auto dfs, int v, int f) -> void {
            sz[v] = 1;
            for (auto [t, w] : gr[v]) {
                if (t != f && !used[t]) {
                    dfs(dfs, t, v);
                    sz[v] += sz[t];
                }
            }
        };
        dfs(dfs, v, -1);
        int f = -1;
        int s = sz[v];
        while (true) {
            auto it = std::find_if(gr[v].begin(), gr[v].end(), [&](auto p) { return p.first != f && !used[p.first] && sz[p.first] > s / 2; });
            if (it == gr[v].end()) {
                break;
            } else {
                f = v;
                v = it->first;
            }
        }
        return v;
    };

    std::vector<int64_t> ans(n, 0);
    auto build = [&](auto build, int v) -> void {
        v = find(v);

        auto dfs = [&](auto dfs, int v, int fr, int cum_left, int sm = 0) -> Fuck {
            sz[v] = 1;
            Fuck f;
            f.push_back(Cum{0, 0, {Shit{K, 1}}});
            for (int ti = 0; ti < gr[v].size(); ti++) {
                auto [t, w] = gr[v][ti];
                if (t == fr) {
                    dp[v][ti] += sm;
                    continue;
                }
                if (used[t]) {
                    continue;
                }

                int sum = int(cum_left - w < 0);
                // dp[v][ti] += sum;
                // ans[v] += sum;

                auto f2 = dfs(dfs, t, v, cum_left - w < 0 ? K - w : cum_left - w, sum);
                sz[v] += sz[t];
                fuck_fisting(f2, w);
                fuck_merge(f, f2);
            }
            return f;
        };

        // struct Cmp {
        //     template <typename T>
        //     bool operator()(const T& a, const T& b) const {
        //         return a.first < b.first;
        //     }
        // };
        std::priority_queue<std::pair<std::pair<int, std::vector<int>>, Cum>> heap;
        for (int ti = 0, xx = 0; ti < gr[v].size(); ti++) {
            auto [t, w] = gr[v][ti];
            if (used[t]) {
                continue;
            }

            Fuck f;
            f.push_back(Cum{0, 0, {}});
            xx = 1;
            auto f2 = dfs(dfs, t, v, K - w);
            int sum = fuck_fisting(f2, w);
            dp[v][ti] += sum;
            fuck_merge(f, f2);

            Cum c(0, 0, {});
            for (auto& c2 : f) {
                c = cum_merge(c, c2);
            }
            heap.push({{-sz[t], {ti}}, std::move(c)});
        }

        while (heap.size() > 1) {
            auto [p1, c1] = heap.top();
            heap.pop();
            auto [p2, c2] = heap.top();
            heap.pop();
            auto [sz1, ti1] = p1;
            auto [sz2, ti2] = p2;

            auto dfs = [&](auto dfs, int v, int f, int fw, int f_id, Cum& c) -> void {
                auto [fisting, sum] = cum_fisting(c, fw);
                // dp[f][f_id] += sum;
                for (int ti = 0; ti < gr[v].size(); ti++) {
                    auto [t, w] = gr[v][ti];
                    if (t == f) {
                        dp[v][ti] += sum;
                        continue;
                    }
                    if (used[t]) {
                        continue;
                    }
                    dfs(dfs, t, v, w, ti, c);
                }
                cum_reverse_fisting(c, fw, fisting);
            };

            for (auto ti : ti1) {
                dfs(dfs, gr[v][ti].first, v, gr[v][ti].second, ti, c2);
            }
            for (auto ti : ti2) {
                dfs(dfs, gr[v][ti].first, v, gr[v][ti].second, ti, c1);
            }

            Cum c = cum_merge(c1, c2);
            ti1.insert(ti1.end(), ti2.begin(), ti2.end());
            heap.push({{sz1 + sz2, ti1}, std::move(c)});
        }

        used[v] = true;
        for (auto [t, w] : gr[v]) {
            if (!used[t]) {
                build(build, t);
            }
        }
    };

    build(build, 0);

    for (int v = 0; v < n; v++) {
        for (int ti = 0; ti < gr[v].size(); ti++) {
            auto [t, w] = gr[v][ti];
            ans[t] += int64_t(dp[v][ti]) * get_sb_sz(t, v);
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << "\n\n"[i == n - 1];
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

750 918
159 63 18
573 310 105
135 400 57
618 27 113
41 265 24
99 576 61
242 85 109
490 88 0
626 721 0
407 446 0
78 644 124
346 198 17
541 504 147
543 423 24
302 450 25
397 344 80
129 607 76
474 59 140
30 10 29
375 260 1
404 81 0
658 695 153
450 100 92
532 249 10
597 151 133
739 714 0
212 345 85
558 ...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #13:

score: 8
Accepted
time: 0ms
memory: 3568kb

input:

2 1
0 1 1

output:

0
0

result:

ok 2 lines

Test #14:

score: 0
Runtime Error

input:

70000 1
50913 18377 1
33894 11911 1
61940 7863 1
61602 33470 1
26341 35575 1
30813 50301 1
2994 67214 1
38527 61714 1
37381 3396 1
43274 14867 1
59352 12066 1
68877 40750 1
44756 43671 1
57921 17977 1
10879 47719 1
26878 13556 1
27329 23697 1
45109 11513 1
21307 12312 1
27202 27807 1
7250 14810 1
27...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Runtime Error

Test #17:

score: 0
Runtime Error

input:

69973 4
44281 27162 1
15299 61302 1
19250 66379 1
45970 65938 1
23683 4445 2
62232 40589 1
37028 58991 2
58769 32024 0
41860 69672 2
14687 10058 2
7874 6780 2
60579 37047 2
739 4096 2
53137 22114 2
35060 21464 0
42597 11591 2
68051 23473 2
61458 35690 2
38719 6601 2
57406 26025 1
38192 41521 0
47941...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%