Submission #1128993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128993		yash_9a3b	Paths (RMI21_paths)	C++20	56 / 100	1095 ms	11332 KiB

Main

#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

//figure out n^2 with bottom up dp
const int N = 1e5 + 5;
int n, k;
vector <pair<int,int> > g[N];
int dp[N], leaf[N];
bitset<100001> seen; 

void dfs(int node, int par){
    if(g[node].size() == 1 && par != -1){
        leaf[node] = node;
        dp[node] = 0;
        seen[node] = true;
        return;
    }
    pair<int,int> mx = mp(-1, -1);
    for(pair<int,int> i : g[node]){
        if(i.f == par) continue;
        dfs(i.f, node);
        dp[leaf[i.f]] += i.s;
        mx = max(mx, mp(dp[leaf[i.f]], leaf[i.f]));
    }
    dp[mx.s] = mx.f;
    leaf[node] = mx.s;
}

signed main()
{
    fast;
    cin >> n >> k;
    for(int i = 1; i < n; i++){
        int a, b, x; cin >> a >> b >> x;
        g[a].push_back(mp(b, x));
        g[b].push_back(mp(a, x));
    }
    for(int i = 1; i <= n; i++){
        seen = 0;
        dfs(i, -1);
        int ans = 0;
        vector <int> all;
        for(int j = 1; j <= n; j++){
            if(leaf[j]) all.push_back(dp[j]); 
        }
        sort(all.rbegin(), all.rend());
        for(int j = 0; j < k; j++) ans += all[j];
        cout << ans << endl;
        for(int j = 1; j <= n; j++){
            leaf[j] = 0;
            dp[j] = 0;
        }
    }
}

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