Submission #1226526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226526		AMnu	Paths (RMI21_paths)	C++20	31 / 100	1092 ms	14188 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN = 1e5+5;

int N, K, x, y, z, cnt;
ll ans[MAXN], sum, dp[MAXN][2];
vector <pii> adj[MAXN];
multiset <ll> inti, sisa;

void ins(ll x) {
    // cout << "ins " << x << endl;
    inti.insert(x);
    sum += x;
    cnt++;
    if (cnt > K) {
        x = *inti.begin();
        sum -= x;
        sisa.insert(x);
        inti.erase(inti.find(x));
        cnt--;
    }
}

void del(ll x) {
    // cout << "del " << x << endl;
    if (sisa.find(x) != sisa.end()) {
        sisa.erase(sisa.find(x));
        return;
    }
    if (inti.find(x) == inti.end()) {
        while (1) {}
    }
    cnt--;
    inti.erase(inti.find(x));
    sum -= x;
    if (!sisa.empty()) {
        x = *sisa.rbegin();
        sum += x;
        inti.insert(x);
        sisa.erase(sisa.find(x));
        cnt++;
    }
}

void root(int cur,int par) {
    ans[cur] = sum;
    for (pii next : adj[cur]) {
        if (next.fi == par) continue;
        ll a = dp[next.fi][0], b;
        if (dp[next.fi][0] + next.se == dp[cur][0]) {
            b = dp[cur][1];
        }
        else {
            b = dp[cur][0];
        }
        dp[next.fi][1] = max(dp[next.fi][1],b+next.se);
        if (dp[next.fi][1] > dp[next.fi][0]) swap(dp[next.fi][0],dp[next.fi][1]);
        del(a + next.se);
        ins(a);
        del(b);
        ins(b + next.se);
        root(next.fi,cur);
        ins(a + next.se);
        del(a);
        ins(b);
        del(b + next.se);
    }
}

void dfs(int cur,int par) {
    if (adj[cur].size() == 1 && cur != 1) {
        ins(0);
    }
    for (pii next : adj[cur]) {
        if (next.fi == par) continue;
        dfs(next.fi,cur);
        del(dp[next.fi][0]);
        ins(dp[next.fi][0]+next.se);
        dp[cur][1] = max(dp[cur][1],dp[next.fi][0]+next.se);
        if (dp[cur][1] > dp[cur][0]) swap(dp[cur][0],dp[cur][1]);
    }
}

int main () {
    cin >> N >> K;
    for (int i=1;i<N;i++) {
        cin >> x >> y >> z;
        adj[x].push_back({y,z});
        adj[y].push_back({x,z});
    }
    dfs(1,1);
    root(1,1);
    for (int i=1;i<=N;i++) {
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32