Submission #598463

#	Time	Username	Problem	Language	Result	Execution time	Memory
598463		CaroLinda	Paths (RMI21_paths)	C++14	56 / 100	425 ms	736 KiB

Main

#include <bits/stdc++.h>

//testing the quadratic

#define ll long long

const int MAXN = 2010;

using namespace std;

int N, K;
int par[MAXN];
ll prof[MAXN];
vector<pair<int,ll> > adj[MAXN];
bool used[MAXN];
ll edgParent[MAXN];

void dfs(int x){
    for(auto &e: adj[x]){
        if(e.first == par[x])
            continue;
        par[e.first] = x;
        prof[e.first]= prof[x]+e.second;
        edgParent[e.first] = e.second;
        dfs(e.first);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for(int i= 1, a, b, c; i < N; i++){
        cin >> a >> b >> c;

        adj[a].push_back(make_pair(b,c));
        adj[b].push_back(make_pair(a,c));
    }

    vector<int> meuVec(N);
    iota(meuVec.begin(),meuVec.end(),1);

    for(int i =1 ; i <= N; i++){
        par[i] = -1;
        prof[i] = 0;
        edgParent[i] = 0;

        dfs(i);

        sort(meuVec.begin(), meuVec.end(), [&](int a, int b){
            return prof[a] > prof[b];
        });

        vector<ll> realVec;

        for(int j = 1; j <= N; j++)
            used[j] = false;

        for(auto j : meuVec){
            ll cur = 0;
            int k = j;


            while(!used[k] && k != i){
                used[k] = true;
                cur += edgParent[k];
                k = par[k];
            }

            realVec.push_back(cur);
        }

        sort(realVec.begin(), realVec.end() );

        ll ans = 0;
        for(int i = N-1; i >= N-K; i--){
            ans += realVec[i];
        }

        cout << ans << "\n";
    }
}

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