Submission #645258

#	Time	Username	Problem	Language	Result	Execution time	Memory
645258		PanTkd	Paths (RMI21_paths)	C++14	36 / 100	694 ms	15580 KiB

Main

//
//  main.cpp
//
//  Created by Panagiotis Chadjicostas on
//  Copyright © Panagiotis Hadjicostas. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#ifdef px
    #define p(x) cerr<<#x<<' '<<x<<endl;
#else
    #define p(x) {}
#endif
#define F first
#define S second
#define sz size
#define ls s,m,idx<<1
#define rs m+1,e,idx<<1|1
const ll MOD=ll(1e9)+7;
const ll MAXN=2*ll(1e6);
///////////////////////////////////////////////////////////////////////
ll N,K;
vector<vii> Adj;
multiset<ll> ms;
ii mp(ll x,ll y){
    ii temp;
    temp.F=x,temp.S=y;
    return temp;
}
ll maxi[10001]={};
void dfs(ll s,ll p){
    maxi[s]=0;
    bool leaf=1;
    for(auto pp: Adj[s]){
        if(pp.F==p)continue;
        leaf=0;
        dfs(pp.F,s);
        ms.erase(ms.find(maxi[pp.F]));
        ms.insert(maxi[pp.F]+pp.S);
        maxi[s]=max(maxi[s],maxi[pp.F]+pp.S);
    }   
    if(leaf){
        ms.insert(0);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N>>K;
    Adj.assign(N+1,vii());

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

        Adj[a].push_back(mp(b,c));
        Adj[b].push_back(mp(a,c));
    }


    for(ll i=1;i<=N;i++){
        ms.clear();
        dfs(i,0);
        vi v;
        
        ll ans=0;
        while (ms.size() > K) {
            ms.erase(ms.begin());
        }
        for (ll x : ms) {
            ans += x;
        }
        cout<<ans<<endl;
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:91:26: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   91 |         while (ms.size() > K) {
      |                ~~~~~~~~~~^~~

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