Submission #1213626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213626		Sir_Ahmed_Imran	Paths (RMI21_paths)	C++17	68 / 100	1108 ms	526688 KiB

Main

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define K 2001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int n, k;
int s[N];
ll ans[N];
int par[N];
ll dp[N][K];
vector<pll> a[N];

void DFS2(int v, int u){
    for(auto & [i, j] : a[v]){
        if(i == u) continue;
        dp[i][2] = dp[v][0] + j;
        if(dp[v][0] == dp[i][0] + j)
            dp[i][2] = dp[v][1] + j;
        dp[i][2] = max(dp[i][2], dp[v][2] + j);
        DFS2(i, v);
    }
}

void DFS(int v, int u){
    for(auto & [i, j] : a[v]){
        if(i == u) continue;
        DFS(i, v);
        dp[v][1] = max(dp[v][1], dp[i][0] + j);
        if(dp[v][0] < dp[v][1])
            swap(dp[v][0], dp[v][1]);
    }
}

void subtask5(){
    DFS(1, 0);
    DFS2(1, 0);
    for(int i = 1; i <= n; i++)
        cout << max(dp[i][0], dp[i][2]) << nl;
}

void dfs(int v, int u){
    if(par[v] == u) return;
    s[v] = 1;
    par[v] = u;
    vector<ll> x; 
    for(auto & [i, j] : a[v]){
        if(i == u) continue;
        dfs(i, v);
        s[v] += s[i];
        x.append(dp[i][1] + j);
        for(int l = 1; l < min(k, s[i]); l++)
            x.append(dp[i][l + 1] - dp[i][l]);
    }
    sort(all(x));
    reverse(all(x));
    for(int i = 0; i < min(k, s[v]); i++){
        dp[v][i + 1] = dp[v][i];
        if(x.size() > i) 
            dp[v][i + 1] += x[i];
    }
}

void get(int v, int u){
    dfs(v, -1);
    ans[v] = dp[v][k];
    for(auto & [i, j] : a[v])
        if(i != u) get(i, v);
}

void solve(){
    int v, u, w;
    cin >> n >> k;
    for(int i = 1; i < n; i++){
        cin >> v >> u >> w;
        a[v].append({u, w});
        a[u].append({v, w});
    }
    if(k == 1)
        return subtask5();
    get(1, 0);
    for(int r = 1; r <= n; r++)
        cout << ans[r] << nl;
}
int terminator(){
    L0TA;
    solve();
    return 0;
}

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