Submission #499718

#	Time	Username	Problem	Language	Result	Execution time	Memory
499718		andrei_boaca	Paths (RMI21_paths)	C++17	36 / 100	1076 ms	19012 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,k,weight[100005],auxw[100005],par[100005],topar[100005],ans,total,tied[100005];
vector<pll> muchii[100005];
vector<int> leaves;
ll bestnode=0;
ll maxim=-1;
ll init[100005],cur[100005],who[100005],c[100005],toprop[100005];
void dfs(ll nod)
{
    init[nod]=0;
    if(muchii[nod].size()==1&&par[nod]!=0)
    {
        init[nod]=1;
        who[nod]=nod;
        leaves.push_back(nod);
        return;
    }
    for(int j=0;j<muchii[nod].size();j++)
    {
        pll i=muchii[nod][j];
        int fiu=i.first;
        int index=i.second;
        if(fiu!=par[nod])
        {
            par[fiu]=nod;
            topar[fiu]=index;
            dfs(fiu);
            init[nod]+=init[fiu];
            if(who[fiu]!=0)
                who[nod]=who[fiu];
        }
    }
    if(init[nod]!=1)
        who[nod]=0;
}
set<pll> s;
void calc(int root)
{
    leaves.clear();
    par[root]=topar[root]=0;
    for(int i=1;i<=n;i++)
    {
        who[i]=0;
        toprop[i]=0;
    }
    s.clear();
    dfs(root);
    ans=total;
    for(int i=1;i<=n;i++)
        cur[i]=init[i];
    for(int j=0;j<leaves.size();j++)
    {
        int i=leaves[j];
        ll cost=0;
        int nod=i;
        while(init[nod]==1&&nod!=root)
        {
            int index=topar[nod];
            cost+=weight[index];
            tied[i]=nod;
            nod=par[nod];
        }
        c[i]=cost;
        s.insert({cost,i});
    }
    ll num=0;
    while(s.size()>k)
    {
        auto it=s.begin();
        ll cost=(*it).first;
        int nod=(*it).second;
        who[nod]=0;
        ans-=cost;
        s.erase(it);
        ll nr=s.size();
        nod=tied[nod];
        cur[nod]=0;
        toprop[nod]=1;
        who[nod]=0;
        while(nod!=root)
        {
            ll p=par[nod];
            cur[p]-=toprop[nod];
            toprop[p]+=toprop[nod];
            toprop[nod]=0;
            if(cur[p]>1)
                break;
            if(cur[p]==0)
                who[p]=0;
            if(cur[p]==1)
            {
                for(int j=0;j<muchii[p].size();j++)
                {
                    pll i=muchii[p][j];
                    int fiu=i.first;
                    if(fiu!=par[p]&&who[fiu]!=0)
                    {
                        who[p]=who[fiu];
                        break;
                    }
                }
                tied[who[p]]=p;
                s.erase({c[who[p]],who[p]});
                c[who[p]]+=weight[topar[p]];
                s.insert({c[who[p]],who[p]});
            }
            nod=p;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
        weight[i]=auxw[i]=c;
        total+=c;
    }
    for(int root=1;root<=n;root++)
    {
        ans=0;
        calc(root);
        cout<<ans<<'\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(ll)':
Main.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int j=0;j<muchii[nod].size();j++)
      |                 ~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<leaves.size();j++)
      |                 ~^~~~~~~~~~~~~~
Main.cpp:71:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   71 |     while(s.size()>k)
      |           ~~~~~~~~^~
Main.cpp:96:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                 for(int j=0;j<muchii[p].size();j++)
      |                             ~^~~~~~~~~~~~~~~~~
Main.cpp:79:12: warning: unused variable 'nr' [-Wunused-variable]
   79 |         ll nr=s.size();
      |            ^~
Main.cpp:70:8: warning: unused variable 'num' [-Wunused-variable]
   70 |     ll num=0;
      |        ^~~

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