제출 #1289256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289256		random_name	Paths (RMI21_paths)	C++20	56 / 100	1094 ms	12652 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> costs(n, -1);
        stack<ll> q;
        stack<ll> visorder;
        costs[r] = 0;
        q.push(r);
        while(!q.empty()){
            ll c = q.top();
            visorder.push(c);
            q.pop();
            for(pair<ll, ll> e:adj[c]){
                if(costs[e.first] != -1) continue;
                costs[e.first] = e.second;
                q.push(e.first);
            }
        }

        vector<ll> sufs(n);
        vector<ll> maxc(n, r);
        while(!visorder.empty()){
            ll c = visorder.top();
            visorder.pop();

            ll msuf=0;
            for(pair<ll, ll> e:adj[c]){
                if(sufs[e.first] > msuf){
                    maxc[c] = e.first;
                    msuf = sufs[e.first];
                }
            }

        
            sufs[c] = msuf + costs[c];
        }

        vector<pair<ll, ll>> sufsorted(n, pair<ll, ll>());
        for(ll i=0;i<n;i++){
            sufsorted[i] = {sufs[i],i};
        }

        sort(sufsorted.begin(), sufsorted.end(), greater<pair<ll, ll>>());

        ll res=0;
        ll ks=0;
        vector<bool> vis(n, false);
        for(ll i=0;i<n;i++){
            bool valid = true;

            // cout << sufsorted[i].second << ':' << sufsorted[i].first << ' ';

            ll cur = sufsorted[i].second;
            do{
                // cout << cur << endl;
                if(vis[cur]){
                    valid = false;
                    break;
                }

                vis[cur] = true;
                cur = maxc[cur];
            } while(cur != r);

            if(!valid) continue;
            
            if(ks == k) break;
            ks++;
            res += sufsorted[i].first;
            

           

        }

        cout << res << '\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