Submission #1213604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213604		Muhammad_Aneeq	Paths (RMI21_paths)	C++20	48 / 100	859 ms	546776 KiB

Main

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define int long long
int const N=1e5+10;
vector<pair<int,int>>nei[N];
multiset<long long>*vl[N]={};
long long dist[N]={};
long long dp[N][2]={};
long long ans[N]={};
int lv=0;
void dfs(int u,int p=0)
{
	bool w=1;
	for (auto [i,c]:nei[u])
	{
		if (i==p) continue;
		w=0;
		dist[i]=dist[u]+c;
		dfs(i,u);
	}
	vl[u]=new multiset<long long>();
	if (w)
		(*vl[u]).insert(dist[u]-dist[p]);
	else
	{
		int v=-1,sz=0;
		for (auto [i,c]:nei[u])
		{
			if (i==p) continue;
			if ((*vl[i]).size()>sz)
			{
				sz=(*vl[i]).size();
				v=i;
			}
		}
		vl[u]=vl[v];
		for (auto [i,c]:nei[u])
		{
			if (i==v||i==p) continue;
			for (auto j:(*vl[i]))
				(*vl[u]).insert(j);
		}
		long long z=*rbegin(*vl[u]);
		(*vl[u]).erase((*vl[u]).find(z));
		z+=dist[u]-dist[p];
		(*vl[u]).insert(z);
	}
}
void ud(int u,int p=0)
{
	for (auto [i,c]:nei[u])
	{
		if (i==p) continue;
		ud(i,u);
		if (dp[u][0]<dp[i][0]+c)
		{
			dp[u][1]=dp[u][0];
			dp[u][0]=dp[i][0]+c;
		}
		else if (dp[u][1]<dp[i][0]+c)
			dp[u][1]=dp[i][0]+c;
	}
}
void bt(int u,long long vl=0,int p=0)
{
	ans[u]=max(dp[u][0],vl);
	for (auto [i,c]:nei[u])
	{
		if (i==p) continue;
		long long mx=vl;
		if (dp[u][0]==dp[i][0]+c)
			mx=max(mx,dp[u][1]);
		else
			mx=max(mx,dp[u][0]);
		bt(i,mx+c,u);
	}
}
inline void solve()
{
	int n,k;
	cin>>n>>k;
	for (int i=1;i<n;i++)
	{
		int u,v,c;
		cin>>u>>v>>c;
		nei[u].push_back({v,c});
		nei[v].push_back({u,c});
	}
	if (k==1)
	{
		ud(1);
		bt(1);
		for (int i=1;i<=n;i++)
			cout<<ans[i]<<endl;
		return;
	}
	for (int i=1;i<=n;i++)
	{
		dist[i]=0;
		dfs(i);
		int z=min((int)((*vl[i]).size()),k);
		long long ans=0;
		while (z--)
		{
			long long f=*rbegin(*vl[i]);
			(*vl[i]).erase((*vl[i]).find(f));
			ans+=f;
		}
		cout<<ans<<endl;
	}
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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