Submission #642788

#	Time	Username	Problem	Language	Result	Execution time	Memory
642788		Tenis0206	Paths (RMI21_paths)	C++11	56 / 100	1086 ms	18788 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];

multiset<int,greater<int>> s;

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

void Add(int val)
{
    s.insert(val);
}

int kmax()
{
    int sum = 0;
    int cnt = 0;
    for(auto it=s.begin();it!=s.end() && cnt<k;it++)
    {
        sum += *it;
        ++cnt;
    }
    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++)
    {
        s.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;
}

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