Submission #1244106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244106		AlperenT_	Tree (IOI24_tree)	C++20	13 / 100	2097 ms	50848 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 = 1e6 + 100 , inf = 1e18 , mod = 998244353;
int n;
std::vector<int> p, w;
vector <int >G[maxn] ;
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) ;
  }
}
int l, r;
ll ans =0 ;
ll sb[maxn] ;

pii dfs2(int v){
  pii a = {inf , 0} ;
  if(sb[v] == l)return a ;
  a.F= w[v] ;
  a.S = v;
  for(int u : G[v]){
    pii b = dfs2(u) ;
    if(b.F < a.F)a =b; 
  }
  return a ;
}

void dfs(int v){
  if(sz(G[v]) == 0){
    sb[v] = l;
    ans += 1ll * l * w[v] ;
    return;  
  }
  sb[v] =0 ;
  for(int u : G[v]){
    dfs(u); 
    sb[v] += sb[u] ;
  }
  while(sb[v] > r){
    pii a = dfs2(v)  ;
    ll x = min(sb[v]-r , sb[a.S] - l) ;
    sb[v] -=x  ;
    ans += x * w[a.S] ;
    int z = a.S; 
    while(z!=v){
      sb[z] -= x ;
      z =p[z] ;
    }
  }
}

long long query(int L, int R) {
  ans = 0; 
  l= L ;
  r = R ;
  dfs(0 );
  return ans ; 
}

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