Submission #642863

#	Time	Username	Problem	Language	Result	Execution time	Memory
642863		Tenis0206	Paths (RMI21_paths)	C++11	56 / 100	1077 ms	18380 KiB

Main

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

using namespace std;

int n,k;

int Max[100005],Max2[100005],d[100005];

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

int l[100005];

int rez[100005];

vector<int> v;

int fr[100005];

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

void Add(int val)
{
    v.push_back(val);
  //  ++fr[val];
}

void Remove(int val)
{
   // --fr[val];
    for(auto it=v.begin();it!=v.end();it++)
    {
        if(*it==val)
        {
            v.erase(it);
            break;
        }
    }
}

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]])
        {
            Max2[nod] = Max[nod];
            Max[nod] = it;
        }
        else if(l[it] + d[it] > l[Max2[nod]] + d[Max2[nod]])
        {
            Max2[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]);
    }
}

void dfs_solve(int nod, int dad = 0, int lsus = 0, bool mergsus = false)
{
    rez[nod] = kmax();
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        if(mergsus)
        {
            int new_l = max(l[it],lsus + d[it]);
            int new_lsus = d[it] + lsus;
            bool new_mergsus = false;
            Remove(lsus);
            Add(new_l);
            Remove(l[it] + d[it]);
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(new_lsus);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(new_lsus);
            }
            Add(l[it] + d[it]);
            Remove(new_l);
            Add(lsus);
            continue;
        }
        if(it!=Max[nod])
        {
            int new_l = max(l[it],l[nod] + d[it]);
            int new_lsus = d[it] + l[nod];
            bool new_mergsus = false;
            Remove(l[nod]);
            Add(new_l);
            Remove(l[it] + d[it]);
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(new_lsus);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(new_lsus);
            }
            Add(l[it] + d[it]);
            Remove(new_l);
            Add(l[nod]);
            continue;
        }
        if(lsus > l[Max2[nod]] + d[Max2[nod]])
        {
            int new_l = max(l[it],lsus + d[it]);
            int new_lsus = d[it] + lsus;
            bool new_mergsus = false;
            Remove(l[nod]);
            Add(new_l);
            Remove(lsus);
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(lsus + d[it]);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(lsus + d[it]);
            }
            Add(lsus);
            Remove(new_l);
            Add(l[nod]);
        }
        else
        {
            int new_l = max(l[it],l[Max2[nod]] + d[Max2[nod]] + d[it]);
            int new_lsus = d[it] + l[Max2[nod]] + d[Max2[nod]];
            bool new_mergsus = false;
            Remove(l[nod]);
            Add(new_l);
            if(Max2[nod])
            {
                Remove(l[Max2[nod]] + d[Max2[nod]]);
            }
            if(new_l!=l[it])
            {
                new_mergsus = true;
                Add(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                new_mergsus = false;
                Add(l[Max2[nod]] + d[Max2[nod]] + d[it]);
            }
            dfs_solve(it,nod,new_lsus,new_mergsus);
            if(new_l!=l[it])
            {
                Remove(l[Max[it]] + d[Max[it]]);
            }
            else
            {
                Remove(l[Max2[nod]] + d[Max2[nod]] + d[it]);
            }
            if(Max2[nod])
            {
                Add(l[Max2[nod]] + d[Max2[nod]]);
            }
            Remove(new_l);
            Add(l[nod]);
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
   // freopen("nr.in","r",stdin);
   // freopen("nr.out","w",stdout);
    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);
    }
    preset(1);
    dfs(1);
    Add(l[1]);
    dfs_solve(1);
    for(int i=1; i<=n; i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int kmax()':
Main.cpp:55: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]
   55 |     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