Submission #643915

#	Time	Username	Problem	Language	Result	Execution time	Memory
643915		Neacsu_Mihai	Paths (RMI21_paths)	C++14	19 / 100	1082 ms	9588 KiB

Main

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

#define NMAX 100000 //o suta de mii
#define INFINIT 100000000000000 //10^14

using namespace std;

vector< pair<int, int> > G[NMAX + 1];
vector <int> frunza;
int tt[NMAX + 1];
int costtt[NMAX + 1];

void DFS(int node, int tata){
    
    for(auto it : G[node]){
        if(it.first != tata){
            tt[it.first] = node;
            costtt[it.first] = it.second;
            DFS(it.first, node);
        }
    }
    
    if(G[node].size() == 1){
        ///este frunza
        frunza.push_back(node);
    }
    
}

long long cost_to_radacina(int node){
    long long rez = 0;
    while(tt[node] != 0){
        rez = rez + 1LL * costtt[node];
        node = tt[node];   
    }
    
    return rez;
}

void update_to_radacina(int node){
    while(tt[node] != 0){
        costtt[node] = 0;
        node = tt[node];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    
    for(int i = 1; i <= N - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    
    for(int rad = 1; rad <= N; rad++){
        frunza.clear();
        for(int i = 1; i <= N; i++){
            tt[i] = 0;
            costtt[i] = 0;
        }
        DFS(rad, 0);
            
        long long bestfinal = 0;
        for(int rep = 1; rep <= K; rep++){
            long long crbest = 0;
            int crnode = -1;
            for(auto it : frunza){
                long long ctorad = cost_to_radacina(it);
                
                if(ctorad > crbest){
                    crbest = ctorad;
                    crnode = it;
                }
            }
            
            bestfinal = bestfinal + crbest;
            update_to_radacina(crnode);
        }
        
        cout << bestfinal << "\n";
    }
        
    return 0;
}

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