Submission #1289283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289283		cansu_mutlu	Paths (RMI21_paths)	C++20	19 / 100	1096 ms	14548 KiB

Main

#include<bits/stdc++.h>
#define int long long 
using namespace std;
//int mxn = 1e6+5;
vector<vector<array<int,2>>> a;
vector<vector<int>> dp;
vector<array<int,2>> ans,f,h;
vector<int> g;
// 0 = node, 1 = miktar;
int k,n;
void dfs(int s,int anne)
{
    for(auto i:a[s])
    {
        int x = i[0];
        int val = i[1];
        if(x==anne) continue;
        dfs(x,s);
        for(int mx = k;mx>0;mx--)
        {
            for(int i = mx-1;i>=0;i--)
            {
                dp[s][mx] = max(dp[s][mx],dp[s][i]+dp[x][mx-i]+val);
            }
        }
    }
}
void d(int s,int anne)
{
    //cout << s << endl;
    f[s][0] = s;
    f[s][1] = 0;
    h[s][0] = s;
    h[s][1] = 0;
    for(auto i:a[s])
    {
        int x = i[0];
        int val = i[1];
       // cout << x << " "<< a.size() << endl;
        if(x==anne) continue;
        d(x,s);
    if(f[s][1]<f[x][1]+val)
        {
            if(h[s][1]<f[s][1]) h[s] = f[s];
            f[s] = {f[x][0],f[x][1]+val};
        }
        else if(h[s][1]<f[x][1]+val)
        {
            h[s] = {f[x][0],f[x][1]+val};
        }
    }
}
void df(int s,int anne,int val)
{
    ans[s] = f[s];
    if(anne!=0)
    {
        
        if(ans[anne][0]!=f[s][0])
        {
            if(ans[anne][1]+val>ans[s][1])
            {
                ans[s] = {ans[anne][0],ans[anne][1]+val};
            }
        }
        g[s] = (g[anne]+val);
        if(f[anne][0]!=f[s][0])
        {
            if(f[anne][1]+val>ans[s][1])
            {
                ans[s] = {f[anne][0],val+f[anne][1]};
            }
        }
        else
        {
            if(h[anne][1]+val>ans[s][1])
            ans[s] = {h[anne][0],h[anne][1]+val};
        }
    }
    for(auto i:a[s])
    {

        int x = i[0];
        int v = i[1];
        //cout << x << " " << s <<  " "<< v << endl;
        if(x==anne) continue;
        df(x,s,v);
    }
}
void dd(int s,int anne)
{
    if(anne!=0)
    {
        if(f[s][0]!=f[anne][0])
        {
            ans[s][1] = max(ans[s][1],g[s]+f[anne][1]);
        }
        else ans[s][1] = max(ans[s][1],g[s]+h[anne][1]);
    }
    for(auto x:a[s])
    {int i = x[0];
        if(i==anne) continue;
    dd(i,s);}
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //int n,k;
    
    cin >> n >> k;
    a.resize(n+1);
    g.resize(n+1,0);
    ans.resize(n+1,{0,0}), f.resize(n+1,{0,0}), h.resize(n+1,{0,0});
    for(int i=0;i<n-1;i++)
    {
        int u,v,x;
        cin >> u >> v >> x;
        a[u].push_back({v,x});
        a[v].push_back({u,x});
    }
   if(k!=1)
   {
     dp.resize(n+1,vector<int>(k+1,0));
    for(int i=1;i<=n;i++) 
   {
     for(int j=0;j<=n;j++)
     {
        for(int t = 0;t<=k;t++) dp[j][t] = 0;
     }
     dfs(i,0);
     cout << *max_element(dp[i].begin(),dp[i].end()) << endl;
   }
   }
   else
   {
    d(1,0);
    df(1,0,0);
    dd(1,0);
    for(int i=1;i<=n;i++) cout << ans[i][1] << endl;
   }
}

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