Submission #1052046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052046		underwaterkillerwhale	Paths (RMI21_paths)	C++17	100 / 100	163 ms	25424 KiB

Main

#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 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32