| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 522553 |
2022-02-05T06:55:28 Z |
fcmalkcin |
Paths (RMI21_paths) |
C++17 |
|
499 ms |
33908 KB |
/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define For(i,a,b) for (ll i=a;i<=b;i++)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn=1e5+100;
const ll mod=998244353 ;
const ll base=2e9+10000;
/// you will be the best but now you just are trash
/// goal 3/7
ll res[maxn];
vector<pll> adj[maxn];
pll st[4*maxn];
ll pos[maxn];
ll n, k;
pll mer(pll a,pll b)
{
if (a.ff>=b.ff)
return a;
return b;
}
void update(ll id,ll left,ll right,ll x,ll diff)
{
if (x>right||x<left)
return ;
if (left==right)
{
st[id]=make_pair(diff,left);
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid,x,diff);
update(id*2+1,mid+1,right,x,diff);
st[id]=mer(st[id*2],st[id*2+1]);
}
pll get(ll id,ll left,ll right,ll x,ll y)
{
if (x>right||y<left)
return make_pair(-1,0);
if (x<=left&&y>=right)
return st[id];
ll mid=(left+right)/2;
return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
struct tk
{
pll st[4*maxn];
ll la[4*maxn];
tk()
{
for (int i=0; i<4*maxn; i++)
{
st[i]=make_pair(0,0);
}
memset(la,0,sizeof(la));
}
pll mer(pll a,pll b)
{
if (a.ff>=b.ff)
return a;
return b;
}
void dosth(ll id,ll left,ll right)
{
st[id*2].ff+=la[id];
st[id*2+1].ff+=la[id];
la[id*2]+=la[id];
la[id*2+1]+=la[id];
la[id]=0;
return ;
}
void update(ll id,ll left,ll right,ll x,ll y,ll diff)
{
if (x>right||y<left)
return ;
if (x<=left&&y>=right)
{
st[id].ff+=diff;
la[id]+=diff;
if (left==right)
st[id].ss=left;
return ;
}
dosth(id,left,right);
ll mid=(left+right)/2;
update(id*2,left,mid,x,y,diff);
update(id*2+1,mid+1,right,x,y,diff);
st[id]=mer(st[id*2],st[id*2+1]);
}
pll get(ll id,ll left,ll right,ll x,ll y)
{
if (x>right||y<left)
return make_pair(-1,0);
if (x<=left&&y>=right)
return st[id];
dosth(id,left,right);
ll mid=(left+right)/2;
return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
} man;
set<pll> st1;
set<pll,greater<pll>> st2;
ll ans=0;
ll cnt=0;
ll f[maxn];
ll l[maxn];
ll dep[maxn];
vector<ll> vt;
ll val[maxn];
bool dd[maxn];
ll anc[maxn];
void add(ll u)
{
if (st1.size()<k)
{
st1.insert(make_pair(val[u],u));
ans+=val[u];
}
else
{
if ((*st1.begin())<make_pair(val[u],u))
{
auto p=(*st1.begin());
st1.erase(st1.begin());
st1.insert(make_pair(val[u],u));
ans+=val[u];
ans-=p.ff;
st2.insert(p);
}
else
{
st2.insert(make_pair(val[u],u));
}
}
}
void ers(ll u)
{
if (st1.count(make_pair(val[u],u)))
{
st1.erase(make_pair(val[u],u));
ans-=val[u];
if (st2.size())
{
auto p=(*st2.begin());
st2.erase(p);
st1.insert(p);
ans+=p.ff;
}
}
else
{
st2.erase(make_pair(val[u],u));
}
}
void change(ll u,ll val1)
{
if (val[u])
{
ers(u);
}
update(1,1,n,f[u],val1);
val[u]=val1;
add(u);
}
void dfs(ll u,ll par)
{
anc[u]=par;
cnt++;
f[u]=cnt;
pos[cnt]=u;
for (auto p:adj[u])
{
ll to=p.ff;
ll w=p.ss;
if (to==par)
continue;
dep[to]=dep[u]+w;
dfs(to,u);
}
l[u]=cnt;
if (l[u]==f[u])
{
vt.pb(u);
}
}
ll mxl[maxn];
void dfs1(ll u,ll par)
{
mxl[u]=u;
for (auto p:adj[u])
{
ll to=p.ff;
ll w=p.ss;
if (to==par)
continue;
dfs1(to,u);
if (val[mxl[to]]>val[mxl[u]])
mxl[u]=mxl[to];
}
}
void dfs2(ll u,ll par,pll mxpre)
{
res[u]=ans;
for (auto p1:adj[u])
{
ll to=p1.ff;
ll w=p1.ss;
if (to==par)
continue;
ll posnxt=mxl[to];
ll valnw=dep[posnxt]-dep[to];
change(posnxt,valnw-w);
auto p=mer(get(1,1,n,f[u],f[to]-1),get(1,1,n,l[to]+1,l[u]));
if (p.ff>mxpre.ff)
{
p=make_pair(p.ff,pos[p.ss]);
}
else
{
p=mxpre;
}
change(p.ss,p.ff+w);
dfs2(to,u,make_pair(p.ff+w,p.ss));
change(posnxt,valnw);
change(p.ss,p.ff);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
cin>> n>> k;
pll root=make_pair(0,1);
for (int i=1; i<=n-1; i++)
{
ll x, y, w;
cin>>x>> y>> w;
adj[x].pb(make_pair(y,w));
adj[y].pb(make_pair(x,w));
root=max(root,make_pair((ll)adj[x].size(),x));
root=max(root,make_pair((ll)adj[y].size(),y));
}
if (n==1)
{
cout <<0;
return 0;
}
dd[0]=1;
dfs(root.ss,0);
// cout <<root.ss<<endl;
k=min(k,(ll)vt.size());
for (auto to:vt)
{
man.update(1,1,n,f[to],l[to],dep[to]);
// cout <<to<<" "<<dep[to]<<endl;
}
for (int i=1; i<=vt.size(); i++)
{
auto p=man.st[1];
ll u=pos[p.ss];
change(u,p.ff);
ll nw=u;
while (!dd[nw])
{
dd[nw]=1;
man.update(1,1,n,f[nw],l[nw],-(dep[nw]-dep[anc[nw]]));
nw=anc[nw];
}
}
dfs1(root.ss,0);
dfs2(root.ss,0,make_pair(-1,0));
for (int i=1;i<=n;i++)
{
cout <<res[i]<<endl;
}
}
Compilation message
Main.cpp: In function 'void add(long long int)':
Main.cpp:129: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 'long long int' [-Wsign-compare]
129 | if (st1.size()<k)
| ~~~~~~~~~~^~
Main.cpp: In function 'void dfs1(long long int, long long int)':
Main.cpp:208:12: warning: unused variable 'w' [-Wunused-variable]
208 | ll w=p.ss;
| ^
Main.cpp: In function 'int main()':
Main.cpp:279:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
279 | for (int i=1; i<=vt.size(); i++)
| ~^~~~~~~~~~~
Main.cpp:251:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
251 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:252:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
252 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
33908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
