QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#150114#5421. Factories Once MorergnerdplayerTL 1ms3516kbC++203.2kb2023-08-25 15:16:062023-08-25 15:16:09

Judging History

This is the latest submission verdict.

  • [2023-08-25 15:16:09]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3516kb
  • [2023-08-25 15:16:06]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap {
    Treap *lc = nullptr, *rc = nullptr;
    int sz = 1;
    unsigned w = rng();
    i64 m = 0, b = 0, val = 0;
};

int size(Treap *t) {
    return t == nullptr ? 0 : t->sz;
}
void apply(Treap *t, i64 m, i64 b) {
    t->m += m;
    t->b += b;
    t->val += m * size(t->lc) + b;
}
void pull(Treap *t) {
    t->sz = size(t->lc) + size(t->rc) + 1;
}
void push(Treap *t) {
    if (t->lc != nullptr) {
        apply(t->lc, t->m, t->b);
    }
    if (t->rc != nullptr) {
        apply(t->rc, t->m, t->b + t->m * (size(t->lc) + 1));
    }
    t->m = t->b = 0;
}

pair<Treap*, Treap*> split(Treap *t, int s) {
    if (t == nullptr) { return {t, t}; }
    push(t);
    Treap *a, *b;
    if (s <= size(t->lc)) {
        b = t;
        tie(a, b->lc) = split(t->lc, s);
    } else {
        a = t;
        tie(a->rc, b) = split(t->rc, s - size(t->lc) - 1);
    }
    pull(t);
    return {a, b};
}

Treap* merge(Treap *t1, Treap *t2) {
    if (t1 == nullptr) { return t2; }
    if (t2 == nullptr) { return t1; }
    if (t1->w > t2->w) {
        t1->rc = merge(t1->rc, t2);
        pull(t1);
        return t1;
    } else {
        t2->lc = merge(t1, t2->lc);
        pull(t2);
        return t2;
    }
}

int rnk(Treap *t, i64 val) {
    int res = 0;
    while (t != nullptr) {
        if (val <= t->val) {
            res += size(t->lc) + 1;
            t = t->rc;
        } else {
            t = t->lc;
        }
    }
    return res;
}

Treap* join(Treap *t1, Treap *t2) {
    Treap *t = nullptr;
    while (t1 != nullptr) {
        auto [u1, v1] = split(t1, 1);
        t1 = v1;
        int r = rnk(t2, u1->val);
        if (r > 0) {
            auto [u2, v2] = split(t2, r);
            t = merge(t, u2);
            t2 = v2;
        }
        t = merge(t, u1);
    }
    t = merge(t, t2);
    return t;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    
    auto solve = [&]() {
        int n, k;
        cin >> n >> k;

        vector<vector<pair<int, int>>> adj(n);
        for (int i = 1; i < n; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
        }
        
        // dp[u][x] = max_{i + j = x} (dp[u][i] + dp[v][j] + w * j * (k - j))
        // dp[u][0] = dp[u][1] = 0
        // maintain slope ? ;

        auto dfs = [&](auto dfs, int u, int p) -> Treap* {
            Treap *tu = new Treap;
            for (auto [v, w] : adj[u]) {
                if (v == p) {
                    continue;
                }
                auto tv = dfs(dfs, v, u);
                apply(tv, -2 * w, 1LL * (k - 1) * w);
                tu = join(tu, tv);
            }
            return tu;
        };
        auto t = dfs(dfs, 0, -1);

        i64 ans = 0;

        while (k--) {
            auto [u, v] = split(t, 1);
            ans += u->val;
            t = v;
        }

        cout << ans << '\n';
    };

    solve();

    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6 3
1 2 3
2 3 2
2 4 1
1 5 2
5 6 3

output:

22

result:

ok 1 number(s): "22"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

4 3
1 2 2
1 3 3
1 4 4

output:

18

result:

ok 1 number(s): "18"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

2 2
1 2 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Time Limit Exceeded

input:

100000 17
37253 35652 9892
56367 53643 1120
47896 49255 4547
93065 88999 1745
5251 6742 5031
49828 50972 8974
31548 46729 1032
56341 56287 4812
21896 22838 1682
82124 90557 7307
76289 76949 7028
33834 45380 6856
15499 15064 2265
10127 5251 9920
87208 93945 9487
68990 72637 6891
91640 85004 2259
4748...

output:


result: