| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 500861 |
2022-01-01T13:30:36 Z |
andrei_boaca |
Paths (RMI21_paths) |
C++17 |
|
449 ms |
524292 KB |
#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
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;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
449 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
