Submission #539442

#	Time	Username	Problem	Language	Result	Execution time	Memory
539442		doowey	Paths (RMI21_paths)	C++14	0 / 100	167 ms	19412 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<pii> T[N];
int par[N];
set<pll> W[N];

void dfs0(int u, int p){
    par[u] = p;
    bool leaf = true;
    pll A;
    for(auto x : T[u]){
        if(x.fi != p){
            leaf = false;
            dfs0(x.fi, u);
            auto it = W[x.fi].end();
            it -- ;
            A = *it;
            A.fi += x.se;
            W[x.fi].erase(it);
            W[x.fi].insert(A);
            if(W[x.fi].size() > W[u].size()){
                swap(W[x.fi], W[u]);
            }
            for(auto y : W[x.fi]){
                W[u].insert(y);
            }
            W[x.fi].clear();
        }
    }
    if(leaf) W[u].insert(mp(0ll, u));
}

ll soln[N];
int mark[N];
ll mx[N];

ll sol;
ll ext;

vector<int> ss;

void dfs1(int u, int pa){
    for(auto x : T[u]){
        if(x.fi == pa) continue;
        dfs1(x.fi, u);
        mark[u] += mark[x.fi];
    }
    if(mark[u] > 0){
        soln[u] = sol;
    }
}

void dfs2(int u, int pa, ll non){
    ll f;
    ext = max(ext, non);
    if(mark[u] == 0) soln[u] = max(soln[u], sol + non);
    for(auto x : T[u]){
        if(x.fi == pa) continue;
        f = non;
        if(mark[x.fi] == 0) f += x.se;
        dfs2(x.fi, u, f);
    }
}

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, k;
    cin >> n >> k;
    int u, v, w;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v >> w;
        T[u].push_back(mp(v, w));
        T[v].push_back(mp(u, w));
    }
    dfs0(1, -1);
    auto it = W[1].end();
    for(int i = 0 ; i < k ; i ++ ){
        if(it == W[1].begin()) break;
        it -- ;
        sol += it->fi;
        mark[it->se] = 1;
        ss.push_back(it->se);
    }
    soln[1]=sol;
    dfs1(1, -1);
    dfs2(1, -1, 0);
    for(auto x : ss){
        soln[x] = max(soln[x], sol + ext);
    }
    for(int i = 1; i <= n; i ++ ){
        cout << soln[i] << "\n";
    }
    return 0;
}

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