oj.uz

Submission #1052046

# Submission time Handle Problem Language Result Execution time Memory
1052046 2024-08-10T11:19:56 Z underwaterkillerwhale Paths (RMI21_paths) C++17
100 / 100
 163 ms 25424 KB 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll BASE = 137;

int n, K, nleaf;
int root;
vector<pll> ke[N];
pll down[N], up[N];

multiset<pll> max_K;
multiset<pll, greater<pll>> values;

ll res = 0;
ll Ans[N];

void dfs (int u, int p) {
    down[u] = MP(0, u);
    if (SZ(ke[u]) == 1) nleaf++;

    iter (&id, ke[u]) {
        ll v, w;
        tie(v, w) = id;
        if (v == p) continue;
        dfs (v, u);
        down[v].fs += w;
        if (down[v].fs > down[u].fs) down[u] = down[v];
    }
    iter (&id, ke[u]) {
        ll v, w;
        tie(v, w) = id;
        if (v == p || down[v].se == down[u].se) continue;
        values.insert(down[v]);
    }
    if (u == root) values.insert(down[root]);
}

void del (pll val) {
    if (values.find(val) != values.end()) values.erase(val);
    else max_K.erase(val), res -= val.fs;
}

void ins (pll val) {
    values.insert(val);
}
void compare () {
    while (SZ(max_K) < K) {
        pll cur = *values.begin();
//        cout << cur.fs <<" "<<cur.se<<"\n";
        values.erase(cur);
        max_K.insert(cur);
        res += cur.fs;
    }
    if (!values.empty() && max_K.begin()->fs < values.begin()->fs) {
        pll u = *values.begin(), v = *max_K.begin();
        max_K.erase(max_K.begin());
        values.erase(values.begin());
        max_K.insert(u);
        values.insert(v);
        res += u.fs - v.fs;
    }
}

void dfs2 (int u, int p) {
    set<pll, greater<pll>> S;
    iter (&id, ke[u]) {
        ll v, w;
        tie(v, w) = id;
        if (v == p) continue;
        S.insert(down[v]);
    }
    iter (&id, ke[u]) {
        ll v, w;
        tie(v, w) = id;
        if (v == p) continue;
        S.erase(down[v]);
        up[v] = MP(up[u].fs + w, up[u].se);
        if (!S.empty()) up[v] = max(up[v], MP(S.begin()->fs + w, S.begin()->se));
        del(down[v]);
        ins(MP(down[v].fs - w, down[v].se));
        del(MP(up[v].fs - w, up[v].se));
        ins(up[v]);
        compare();
//        cout << v <<":\n";
//        cout << up[v].fs<<","<<up[v].se <<"\n";
//        cout << "val: "; iter (&id, values) cout << id.fs<<","<<id.se<<" ";
//        cout<<"\n";
//        cout << "max_K: "; iter (&id, max_K) cout << id.fs<<","<<id.se<<" ";
//        cout<<"\n";
        Ans[v] = res;

        dfs2 (v, u);

        S.insert(down[v]);
        del(MP(down[v].fs - w, down[v].se));
        ins(down[v]);
        del(up[v]);
        ins(MP(up[v].fs - w, up[v].se));
        compare();


    }
}

void solution () {
    cin >> n >> K;
    rep (i, 1, n - 1) {
        ll u, v, w;
        cin >> u >> v >> w;
        ke[u].pb({v, w});
        ke[v].pb({u, w});
    }
    if (n == 2) {
        rep (i, 1, K) cout << ke[1][0].se <<"\n";
        return;
    }
    if (SZ(ke[1]) == 1) root = ke[1][0].fs;
    else root = 1;
    dfs(root, 0);
    K = min(K, nleaf);
    compare();
    Ans[root] = res;
    dfs2 (root, 0);
    rep (i, 1, n) cout << Ans[i] <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".ans","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +2
2 + 8 * 2 - 9

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6552 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6552 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6564 KB Output is correct
11 Correct 3 ms 6492 KB Output is correct
12 Correct 3 ms 6488 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6552 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6564 KB Output is correct
11 Correct 3 ms 6492 KB Output is correct
12 Correct 3 ms 6488 KB Output is correct
13 Correct 3 ms 6744 KB Output is correct
14 Correct 3 ms 6896 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 3 ms 6748 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 18176 KB Output is correct
2 Correct 155 ms 24144 KB Output is correct
3 Correct 97 ms 15368 KB Output is correct
4 Correct 140 ms 19148 KB Output is correct
5 Correct 134 ms 20816 KB Output is correct
6 Correct 160 ms 20232 KB Output is correct

Subtask #6
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6552 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 3 ms 6492 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6564 KB Output is correct
11 Correct 3 ms 6492 KB Output is correct
12 Correct 3 ms 6488 KB Output is correct
13 Correct 3 ms 6744 KB Output is correct
14 Correct 3 ms 6896 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 3 ms 6748 KB Output is correct
17 Correct 3 ms 6748 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Correct 158 ms 18176 KB Output is correct
21 Correct 155 ms 24144 KB Output is correct
22 Correct 97 ms 15368 KB Output is correct
23 Correct 140 ms 19148 KB Output is correct
24 Correct 134 ms 20816 KB Output is correct
25 Correct 160 ms 20232 KB Output is correct
26 Correct 148 ms 18512 KB Output is correct
27 Correct 133 ms 23888 KB Output is correct
28 Correct 135 ms 25424 KB Output is correct
29 Correct 100 ms 15700 KB Output is correct
30 Correct 155 ms 19656 KB Output is correct
31 Correct 134 ms 16724 KB Output is correct
32 Correct 144 ms 21504 KB Output is correct
33 Correct 163 ms 18512 KB Output is correct
34 Correct 88 ms 15300 KB Output is correct
35 Correct 150 ms 19660 KB Output is correct
36 Correct 121 ms 25172 KB Output is correct