| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038345 |
2024-07-29T17:12:14 Z |
manizare |
Paths (RMI21_paths) |
C++14 |
|
409 ms |
524288 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 10 , N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333 , inf = 1e9 +100 , maxk = 2022 ;
int n , k , mark[maxn] , id[maxn] , par[maxn] , st[maxn] , en[maxn] , c = 1 , pw[maxn] , dis[maxn] , ans[maxn] ;
vector <pii> G[maxn] ;
struct node{
pii mx , mn ;
int lz = 0 ;
};
node operator+(node a , node b){
node r ;
r.mx.F = max(a.mx.F , b.mx.F) ;
if(r.mx.F == a.mx.F)r.mx.S = a.mx.S ;
else r.mx.S = b.mx.S ;
r.mn.F = min(a.mn.F , b.mn.F) ;
if(r.mn.F == a.mn.F)r.mn.S = a.mn.S ;
else r.mn.S = b.mn.S ;
r.lz = 0 ;
return r ;
}
struct segtree{
vector <pair<int,node> > his ;
node s[4*maxn] ; int sm =0 , ok =0 ;
void bui(int p = 1, int l = 1 ,int r =n){
int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
sm =0 ;
if(l == r){
s[p].mx = {0,l} ;
s[p].mn = {0,l} ;
return ;
}
bui(pl,l,mid) ;
bui(pr ,mid+1,r);
s[p] = s[pl] + s[pr] ;
}
void shi(int p){
int pl =p<<1 , w = s[p].lz ,pr =p<<1|1 ;
his.pb({pl,s[pl]}) ;his.pb({pr,s[pr]});
s[pl].lz += w ;
s[pr].lz += w ;
s[pr].mx.F += w ;
s[pl].mn.F += w ;
s[pl].mx.F += w ;
s[pr].mn.F += w;
s[p].lz =0 ;
}
void upd(int le ,int ri , int w ,int p = 1,int l =1 ,int r =n){
his.pb({p,s[p]}) ;
int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
if(l > ri || le > r)return;
if(le <= l && r<= ri){
s[p].mx.F += w;
s[p].mn.F += w;
s[p].lz += w;
sm += w;
return ;
}
shi(p) ;
upd(le,ri,w,pl,l,mid);
upd(le,ri,w,pr,mid+1,r);
s[p] = s[pl] + s[pr] ;
}
node que(int le ,int ri , int p =1 ,int l =1 ,int r =n){
int mid = (l+r)/2 ,pl=p<<1, pr =p<<1|1 ;
if(le <= l && r <= ri)return s[p] ;
his.pb({p,s[p]}) ;
shi(p) ;
if(mid >= ri)return que(le,ri,pl,l,mid);
if(mid < le)return que(le,ri,pr,mid+1,r);
return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}
void rem(int x , int p =1 ,int l = 1, int r =n){
his.pb({p,s[p]}) ;
int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
if(l > x || x > r)return ;
if(l == r){
sm -= s[p].mx.F ;
s[p].mx = {-inf,l} ;
s[p].mn = {inf,l} ;
return ;
}
rem(x,pl,l,mid);rem(x,pr,mid+1,r);
s[p] = s[pl]+s[pr] ;
}
void add(int x ,int w , int p =1 , int l =1 ,int r = n){
his.pb({p,s[p]}) ;
int mid = (l+r)/2 , pl=p<<1 ,pr =p<<1|1 ;
if(l > x || x > r)return ;
if(l == r){
sm += w;
s[p].mx = {w,l} ;s[p].mn = {w,l} ;
return ;
}
add(x,w,pl,l,mid);add(x,w,pr,mid+1,r) ;
s[p] = s[pl] + s[pr] ;
}
};
segtree v0 , v1 ;
void dfs(int v ,int p =0){
st[v] = c ; c++ ;
id[st[v]] = v;
for(auto [u,w] : G[v]){
if(u == p)continue ;
par[u] = v ;
pw[u] = w;
dis[u] = dis[v] + w;
dfs(u ,v) ;
}
en[v] = c-1 ;
}
void ch(vector <pii> vec , int w){
node r1, r2 ;
rep(i , 0, sz(vec)-1){
int l =vec[i].F , r = vec[i].S ;
node x = v0.que(l,r);
if(i == 0){
r1 = x ;
}else{
r1 = x + r1 ;
}
}
rep(i , 0, sz(vec)-1){
int l =vec[i].F , r = vec[i].S ;
node x = v1.que(l,r);
if(i == 0){
r2 = x ;
}else{
r2 = x + r2 ;
}
}
if(r2.mx.F > r1.mx.F){
// cout << "1 " << r2.mx.S << " " << w << "<--\n" ;
v1.upd(r2.mx.S , r2.mx.S , w) ;
}else{
// cout << "0 " << r1.mx.S << " " << w << "<--\n" ;
v0.upd(r1.mx.S , r1.mx.S , w) ;
}
}
void cp(){
rep(i , 1 , n){
cout << max(-1ll,v1.que(i,i).mx.F) << " " ;
}
cout << "\n" ;
rep(i ,1, n){
cout << max(-1ll,v0.que(i,i).mx.F) << " " ;
}
cout << "\n" ;
}
void dfs2(int v ,int p =0){
//if(v == 9)cp() ;
ans[v] = v1.sm ;
for(auto [u,w] : G[v]){
if(u == p)continue ;
if(v == 1 && u == 7)cp() ;
v1.sm = ans[v] ;
v1.his.clear() ; v0.his.clear() ;
vector <pii> az ; az.pb({st[u],en[u]}) ;ch(az,-w) ;
az.clear() ;
if(st[u] != 1)az.pb({1,st[u]-1});
if(en[u]!=n)az.pb({en[u]+1,n});
ch(az,w) ;
while(v1.s[1].mn.F < v0.s[1].mx.F){
pii a = v1.s[1].mn , b = v0.s[1].mx ;
v0.add(a.S,a.F) ;
v1.add(b.S,b.F) ;
v1.rem(a.S) ;
v0.rem(b.S) ;
}
vector <pair<int,node> > u1= v1.his , u0 = v0.his ;
dfs2(u ,v) ;
while(sz(u1)) {
int p = u1.back().F ;
v1.s[p] =u1.back().S ;
u1.pop_back() ;
}
while(sz(u0)) {
int p = u0.back().F ;
v0.s[p] =u0.back().S ;
u0.pop_back() ;
}
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> k ;
rep(i ,1, n-1){
int v, u , w ;
cin >> v >> u >> w;
G[v].pb({u,w});
G[u].pb({v,w}) ;
}
dfs(1) ;
v1.bui() ;
rep(i ,1 ,n){
v1.upd(st[i],st[i] , dis[i]) ;
}
v0.bui() ;
rep(i ,1, n){
int a = id[v1.s[1].mx.S];
int ca = a ;
int s = 0 ;
while(a != 0){
if(mark[a] == 1)break ;
mark[a] =1 ;
s += pw[a] ;
v1.upd(st[a],en[a] , -pw[a]) ;
a = par[a] ;
}
v0.upd(st[ca], st[ca] , s) ;
}
v1.bui() ;
rep(i , 1,n)mark[i] = 0 ;
rep(i ,1, k){
pii a = v0.s[1].mx ;
v0.rem(a.S) ;
v1.add(a.S , a.F) ;
mark[a.S] = 1 ;
}
v1.ok = 1;
rep(i , 1,n){
if(mark[i] == 1)continue;
v1.rem(i) ;
}
cp() ;
dfs2(1) ;
rep(i ,1 ,n){
cout << ans[i] << "\n" ;
}
}
Compilation message
Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
123 | for(auto [u,w] : G[v]){
| ^
Main.cpp: In function 'void dfs2(long long int, long long int)':
Main.cpp:176:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
176 | for(auto [u,w] : G[v]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
409 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
39516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
