Submission #1244149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244149		AlperenT_	Tree (IOI24_tree)	C++20	0 / 100	2095 ms	21316 KiB

tree

#include "tree.h"
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.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--)
#define ld double
#define ll long long 
using namespace std ;
const ll maxn = 1e5 + 100 , inf = 1e18 , mod = 998244353;
int n;
std::vector<int> p, w;
int h[maxn]  , sz[maxn] ;
vector <int >G[maxn] ;
void bui(int v){
  sz[v] = 1;
  for(int u : G[v]){
    bui(u);
    sz[v] += sz[u] ;
  }
}
int st[maxn] , en[maxn] , id[maxn] , cnt = 0 ;
ll l , r, ans =0 ; 
vector <int> tp ;
void bui2(int v){
  vector <pii> vec;
  id[v] = cnt ;
  tp.pb(v) ;
  st[v] = cnt ;
  cnt++ ;
  for(int u : G[v]){
    vec.pb({sz[u] , u});
  } 
  sort(all(vec));
  reverse(all(vec));
  rep(i , 0 ,sz(vec)-1){
    int u = vec[i].S ; 
    if(i ==0 ){
      h[u] = h[v] ;
      bui2(u);
    }else{
      h[u] = u;
      bui2(u);
    }
  }
  en[v] = cnt-1 ;
}
struct node{
  ll mn , sm  ,id ;
  node(){
    mn = sm = id =0 ;
  }
};node seg[4*maxn] ;
node operator+(node a , node b){
  node r ;
  r.mn = min(a.mn , b.mn) ; ;r.id = a.id;
  if(r.mn == b.mn)r.id = b.id ;
  r.sm  =0 ;
  return r ;
}

void buiseg(int p = 1, int l = 0 , int r = n-1){
  int mid = (l+r)/2 ,pl=p<<1,pr=p<<1|1;
  if(l == r){
    seg[p].mn = w[tp[l]];
    seg[p].id = l ; 
    seg[p].sm =0 ;
    return ;
  }
  buiseg(pl,l,mid);
  buiseg(pr ,mid+1,r);
  seg[p] = seg[pl] + seg[pr];
}

void shi(int p){
  int pl= p<<1 , pr =p<<1|1 ;
  seg[pl].sm+= seg[p].sm ;
  seg[pr].sm+= seg[p].sm ;
  seg[p].sm =0 ;
}

void upd(int le , int ri , int w , int p =1 , int l =0  , int r = n-1){
  int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
  if(le > r || l > ri)return; 
  if(le <= l && r <= ri){
    seg[p].sm += w ;
    return; 
  }
  shi(p);
  upd(le,ri,w,pl,l,mid);
  upd(le,ri,w,pr,mid+1,r);
  seg[p] = seg[pl] + seg[pr];
}
node que(int le ,int ri , int p =1 ,int l = 0,int r =n-1){
  int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
  if(le <= l && r <=ri)return seg[p];
  shi(p) ;
  if(ri <= mid)return que(le,ri,pl,l,mid);
  if(le > mid)return que(le,ri,pr,mid+1,r);
  return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r);
}

void msir(int v, int w){
  if(h[v]==0){
    upd(0 , id[v] , w) ;
    return ;
  }
  upd(id[h[v]] , id[v] , w) ;
  v = p[h[v]] ;
  msir(v, w) ;  
}

void init(std::vector<int> P, std::vector<int> W) {
  p = P;
  w = W;
  n = (int)p.size();
  rep(i ,1, n-1){
    G[p[i]].pb(i) ;
  }
  bui(0);bui2(0);
}

void rem(int x, int p =1 , int l =0  , int r = n-1){
  int mid = (l+r)/2 , pl=p<<1, pr=p<<1|1;
  if(x > r || l > x)return; 
  if(l == r){
    seg[p].mn = inf ;
    return; 
  }
  shi(p);
  rem(x,pl,l,mid);
  rem(x,pr,mid+1,r);
  seg[p] = seg[pl] + seg[pr];
}
int f(int v){return que(v,v).sm  ;}

void dfs(int v){
  if(sz(G[v]) == 0){
    msir(v,  l) ;
    ans += 1ll * l * w[v] ;
    return;  
  }
  for(int u : G[v]){
    dfs(u); 
  }
  while(f(v) > r){
    node a =que(st[v] , en[v]) ;
    int u = tp[a.id] ;
    if(f(u) == l){
      rem(a.id);
      continue ;
    }
    ll x = min(f(v)-r ,f(u) - l) ;
    ans += x * w[u] ; 
    msir(u, -x) ;
  }
}

long long query(int L2, int R2) {
  buiseg();
  ans = 0; 
  l= L2 ;
  r= R2 ;
  dfs(0 );
  return ans ; 
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19