Submission #1289232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289232		random_name	Paths (RMI21_paths)	C++20	19 / 100	1096 ms	11196 KiB

Main

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

int main(){
    ll n,k;cin>>n>>k;
    vector<vector<pair<ll,ll>>> adj(n);
    for(ll i=1;i<n;i++){
        ll a,b,c; cin>>a>>b>>c;
        adj[a-1].push_back({b-1,c});
        adj[b-1].push_back({a-1,c});
    }

    for(ll r=0;r<n;r++){
        vector<ll> parents(n,-1);
        vector<ll> prefs(n, 0);
        vector<ll> leafs;
        stack<ll> q;
        q.push(r);
        parents[r] = r;
        while(!q.empty()){
            ll c=q.top();
            q.pop();
            bool leaf = true;
            for(pair<ll, ll> e:adj[c]){
                if(parents[e.first] != -1){
                    continue;
                }

                leaf = false;

                parents[e.first] = c;
                prefs[e.first] = prefs[c] + e.second;
                q.push(e.first);
            }

            if(leaf)
                leafs.push_back(c);
        }
        // for(ll i:parents)
        //     cout << i << ' ';
        // cout << '\n';

        vector<bool> vis(n, false);
        vis[r] = true;
        ll res=0;
        for(ll i=0;i<k;i++){
            pair<ll, ll> mincost = {0, 0};
            vector<ll> vispref(n, -1);
            for(ll j:leafs){
                ll cur = j;
                stack<ll> visq;
                while(!vis[cur] && vispref[cur] == -1){
                    visq.push(cur);
                    cur = parents[cur];
                }

                if(vis[cur])
                    vispref[cur] = prefs[cur];
                
                while(!visq.empty()){
                    vispref[visq.top()] = vispref[cur];
                    visq.pop();
                }

                if(prefs[j] - vispref[j] > mincost.first){
                    mincost = {prefs[j] - vispref[j], j};
                }
            }

            res += mincost.first;
            ll cur = mincost.second;
            while(!vis[cur]){
                vis[cur] = true;
                cur = parents[cur];
            }
        }

        cout << res << '\n';


    }
}

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