Submission #642783

#	Time	Username	Problem	Language	Result	Execution time	Memory
642783		Tenis0206	Paths (RMI21_paths)	C++11	56 / 100	1075 ms	18900 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

int n,k;

int Max[100005],d[100005];

vector<pair<int,int>> Gaux[100005];
vector<int> G[100005];

int l[100005];

vector<int> v;

void debug(vector<int> c)
{
    for(auto it : c)
    {
        cerr<<it<<' ';
    }
    cerr<<'\n';
}

void Add(int val)
{
    v.push_back(val);
}

int kmax()
{
    int sum = 0;
    sort(v.begin(),v.end(),greater<int>());
  //  debug(v);
    for(int i=0;i<k && i<v.size();i++)
    {
        sum += v[i];
    }
    return sum;
}

void preset(int nod, int dad = 0)
{
    for(auto it : Gaux[nod])
    {
        if(it.first==dad)
        {
            continue;
        }
        preset(it.first,nod);
        d[it.first] = it.second;
    }
}

void dfs(int nod, int dad = 0)
{
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        dfs(it,nod);
        if(l[it] + d[it] > l[Max[nod]] + d[Max[nod]])
        {
            Max[nod] = it;
        }
    }
    l[nod] = l[Max[nod]] + d[Max[nod]];
    for(auto it : G[nod])
    {
        if(it==dad || it==Max[nod])
        {
            continue;
        }
        Add(l[it] + d[it]);
    }
}

signed main()
{
    cin>>n>>k;
    for(int i=1; i<n; i++)
    {
        int x,y,c;
        cin>>x>>y>>c;
        Gaux[x].push_back({y,c});
        Gaux[y].push_back({x,c});
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
    {
        v.clear();
        for(int j=1;j<=n;j++)
        {
            Max[j] = 0, d[j] = 0, l[j] = 0;
        }
        preset(i);
        dfs(i);
        Add(l[i]);
        cout<<kmax()<<'\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int kmax()':
Main.cpp:36:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<k && i<v.size();i++)
      |                        ~^~~~~~~~~

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