Submission #500861

#	Time	Username	Problem	Language	Result	Execution time	Memory
500861		andrei_boaca	Paths (RMI21_paths)	C++17	0 / 100	449 ms	524292 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n,k,par[100005];
vector<pii> muchii[100005];
ll weight[100005],nr[100005],sol[100005],topar[100005];
vector<vector<ll>> dp;
bool use[100005];
bool comp(pii a, pii b)
{
    return nr[a.first]>nr[b.first];
}
void dfs(int nod)
{
    if(muchii[nod].size()==1&&par[nod]!=0)
    {
        nr[nod]=1;
        dp[nod].resize(2);
        dp[nod][1]=0;
        return;
    }
    vector<pii> v;
    for(auto i:muchii[nod])
    {
        int fiu=i.first;
        if(fiu!=par[nod])
        {
            par[fiu]=nod;
            topar[fiu]=weight[i.second];
            dfs(fiu);
            nr[nod]+=nr[fiu];
            v.push_back({fiu,weight[i.second]});
        }
    }
    int lg=min(nr[nod],k*1LL)+1;
    dp[nod].resize(lg);
    sort(v.begin(),v.end(),comp);
    int x=v[0].first;
    int y=v[0].second;
    for(int i=1;i<=min(nr[x],k*1LL);i++)
        dp[nod][i]=max(dp[nod][i],dp[x][i]+y);
    ll suma=nr[x];
    for(int i=1;i<v.size();i++)
    {
        x=v[i].first;
        y=v[i].second;
        vector<ll> aux;
        suma+=nr[x];
        suma=min(suma,k);
        aux.resize(suma+1);
        for(int i=1;i<=nr[x];i++)
            for(int s=i;s<=suma&&s<dp[nod].size();s++)
                aux[s]=max(aux[s],max(dp[nod][s],dp[nod][s-i]+dp[x][i]+y));
        dp[nod]=aux;
    }
}
void recalc(int nod)
{
    if(muchii[nod].size()==1&&par[nod]!=0)
    {
        nr[nod]=1;
        dp[nod].resize(2);
        dp[nod][1]=0;
        return;
    }
    vector<pii> v;
    nr[nod]=0;
    dp[nod].clear();
    for(auto i:muchii[nod])
    {
        int fiu=i.first;
        if(fiu!=par[nod])
        {
            par[fiu]=nod;
            nr[nod]+=nr[fiu];
            v.push_back({fiu,weight[i.second]});
        }
    }
    int lg=min(nr[nod],k*1LL)+1;
    dp[nod].resize(lg);
    sort(v.begin(),v.end(),comp);
    int x=v[0].first;
    int y=v[0].second;
    for(int i=1;i<=min(nr[x],k*1LL);i++)
        dp[nod][i]=max(dp[nod][i],dp[x][i]+y);
    ll suma=nr[x];
    for(int i=1;i<v.size();i++)
    {
        x=v[i].first;
        y=v[i].second;
        vector<ll> aux;
        suma+=nr[x];
        suma=min(suma,k);
        aux.resize(suma+1);
        for(int i=1;i<=nr[x];i++)
            for(int s=i;s<=suma&&s<dp[nod].size();s++)
                aux[s]=max(aux[s],max(dp[nod][s],dp[nod][s-i]+dp[x][i]+y));
        dp[nod]=aux;
    }
}
void reroot(int nod,int fiu)
{
    par[nod]=fiu;
    topar[nod]=topar[fiu];
    topar[fiu]=0;
    par[fiu]=0;
    recalc(nod);
    vector<ll> aux;
    nr[fiu]+=nr[nod];
    aux.resize(nr[fiu]+1);
    dp[fiu].resize(nr[fiu]+1);
    ll y=topar[nod];
    for(int i=1;i<=min(k,nr[nod]);i++)
        for(int s=i;s<=min(k,nr[fiu]);s++)
        {
            ll val=dp[nod][i]+dp[fiu][s-i]+y;
            ll depeu=dp[nod][i];
            aux[s]=max(aux[s],max(dp[fiu][s],dp[nod][i]+dp[fiu][s-i]+y));
        }
    dp[fiu]=aux;
}
void calc(int nod)
{
    use[nod]=1;
    if(k<dp[nod].size())
        sol[nod]=dp[nod][k];
    else
        sol[nod]=dp[nod][(int)dp[nod].size()-1];
    for(auto i:muchii[nod])
    {
        int fiu=i.first;
        int w=weight[i.second];
        int index=i.second;
        if(fiu!=par[nod]&&!use[fiu])
        {
            reroot(nod,fiu);
            calc(fiu);
            reroot(fiu,nod);
        }
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        weight[i]=c;
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
    }
    dp.resize(n+5);
    dfs(1);
    calc(1);
    for(int i=1;i<=n;i++)
        cout<<sol[i]<<'\n';
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int)':
Main.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i=1;i<v.size();i++)
      |                 ~^~~~~~~~~
Main.cpp:55:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int s=i;s<=suma&&s<dp[nod].size();s++)
      |                                  ~^~~~~~~~~~~~~~~
Main.cpp: In function 'void recalc(int)':
Main.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=1;i<v.size();i++)
      |                 ~^~~~~~~~~
Main.cpp:99:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for(int s=i;s<=suma&&s<dp[nod].size();s++)
      |                                  ~^~~~~~~~~~~~~~~
Main.cpp: In function 'void reroot(int, int)':
Main.cpp:119:16: warning: unused variable 'val' [-Wunused-variable]
  119 |             ll val=dp[nod][i]+dp[fiu][s-i]+y;
      |                ^~~
Main.cpp:120:16: warning: unused variable 'depeu' [-Wunused-variable]
  120 |             ll depeu=dp[nod][i];
      |                ^~~~~
Main.cpp: In function 'void calc(int)':
Main.cpp:128:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     if(k<dp[nod].size())
      |        ~^~~~~~~~~~~~~~~
Main.cpp:135:13: warning: unused variable 'w' [-Wunused-variable]
  135 |         int w=weight[i.second];
      |             ^
Main.cpp:136:13: warning: unused variable 'index' [-Wunused-variable]
  136 |         int index=i.second;
      |             ^~~~~

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