Submission #1289267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289267		efeg	Paths (RMI21_paths)	C++20	56 / 100	132 ms	12876 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


#define int long long
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define endl '\n'

typedef vector<int> vi;
typedef pair<long long,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef tuple<int,int,int> iii;


int n,k,leafcnt; 
vector<vii> adj;
vi bestup;  
vi dist;
vii par; 
vii best; 

int dfs(int node,int p){
    int mxdist = 0,mxleaf = node;
    for (auto tp : adj[node]){
        int to,w; tie(to,w) = tp; 
        if (to == p) continue; 
        int leaf = dfs(to,node); 
        dist[leaf] += w; 
        
        if (adj[to].size() == 1) leafcnt++; 
        if (dist[leaf] > mxdist){
            mxleaf = leaf;
            mxdist = dist[leaf]; 
        }
    }
    return mxleaf; 
}

void cal(int node,int p){
    for (auto tp : adj[node]){
        int to,w; tie(to,w) = tp; 
        if (to == p) continue; 
        cal(to,node); 
        par[to] = {node,w}; 
        if (best[node].F <= best[to].F + w){
            if (best[node].S != -1) best[node].S = max(best[node].F,best[to].S + w); 
            else best[node].S = best[node].F; 

            best[node].F = best[to].F + w; 
        }
        else if (best[node].S != -1 && best[node].S < best[to].F + w){
            best[node].S = best[to].F + w; 
        }
    }
}

void ters(int node,int p){
    for (auto tp : adj[node]){
        int to,w; tie(to,w) = tp;
        if (to == p) continue; 
        if (best[node].F == w + best[to].F) bestup[to] = w + best[node].S;
        else bestup[to] = w + best[node].F;
        bestup[to] = max(bestup[to],bestup[node] + w); 
        ters(to,node); 
    }
}

void solve1(); 
void solve2(); 

int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(NULL); cout.tie(NULL);  
    cin >> n >> k; 
    adj.assign(n + 10,vii()); 
    
    for (int i = 0; i < n-1; i++){
        int u,v,w; cin >> u >> v >> w; u--; v--; 
        adj[u].eb(v,w); 
        adj[v].eb(u,w); 
    }

    if (k == 1) solve1(); 
    else solve2(); 
    
    
    return 0; 
    
}

void solve2(){
    for (int root = 0; root < n; root++){
        leafcnt = 0; 
        dist.assign(n,0); 
        dfs(root,-1); 

        sort(all(dist),greater<int>());

        int ans = 0; 
        for (int i = 0; i < min(k,leafcnt); i++) ans += dist[i]; 
        cout << ans << endl; 
    
    }
}

void solve1(){
    best.assign(n + 10,{0,-1}); 
    par.assign(n + 10,{-1,-1}); 
    bestup.assign(n +10 ,0); 
    cal(0,-1); 
    ters(0,-1); 
    for (int root = 0; root < n; root++){
        cout << max(best[root].F,bestup[root]) << endl; 
    }
}

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