Submission #1134656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134656		ten_xd	Tree (IOI24_tree)	C++20	0 / 100	45 ms	15428 KiB

tree

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
#include "tree.h"

const int N = 1e5+5432, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

struct Element
{
  ll val,su;
  bool operator < (const Element &element) const
  {
    return val < element.val;
  }
};

ll n,q,l,r,res;
vector<ll> G[N];
multiset<Element> us[N];
ll su_us[N], C[N];

std::vector<int> p, w;

void DFS(int v)
{
  su_us[v] = 0, us[v].clear(), C[v] = 0;
  for(auto x : G[v])
  {
    if(x == p[v]) continue;
    DFS(x);
    su_us[v] += su_us[x], C[v] += C[x];
    for(auto it = us[x].begin(); it != us[x].end(); ++it) us[v].insert(*it);
  }
  if(C[v] == 0)
  {
    C[v] = l, res += C[v]*abs(w[v]), us[v].insert({w[v],r-l}), su_us[v] += r-l;
  }
  else
  {
    us[v].insert({w[v],(ll)2e6}), su_us[v] += (ll)2e6;
    while(C[v] > r)
    {
      int roz = C[v]-r;
      Element at = *us[v].begin();
      us[v].erase(us[v].find(at));
      if(at.su <= roz)
      {
        C[v] -= at.su, su_us[v] -= at.su, res += at.val*at.su;
      }
      else
      {
        C[v] -= roz, su_us[v] -= roz, res += at.val*roz;
        us[v].insert({at.val,at.su-roz});
      }
    }
    while(su_us[v] > C[v]-l)
    {
      ll roz = su_us[v]-(C[v]-l);
      Element at = *us[v].rbegin();
      us[v].erase(us[v].find(at));
      if(at.su <= roz)
      {
        su_us[v] -= at.su;
      }
      else
      {
        su_us[v] -= roz, us[v].insert({at.val,at.su-roz});
      }
    }
  }
}

void init(std::vector<int> P, std::vector<int> W) {
  p = P;
  w = W;
  n = (int)p.size();

  for(int i = 1; i < n; ++i)
  {
    G[p[i]].pb(i);
  }
}

long long query(int L, int R) {
  res = 0, l = L, r = R;
  DFS(0);

  return res;
}

• 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