제출 #1134686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134686		ten_xd	트리 (IOI24_tree)	C++20	13 / 100	2098 ms	45332 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"

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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

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

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

std::vector<int> p, w;

void merguj(ll a, ll b)
{
  if((int)us[idx[a]].size() < (int)us[idx[b]].size())
  {
    su_us[idx[b]] += su_us[idx[a]];
    for(auto it = us[idx[a]].begin(); it != us[idx[a]].end(); ++it) us[idx[b]].insert(*it);
    idx[a] = idx[b];
  }
  else
  {
    su_us[idx[a]] += su_us[idx[b]];
    for(auto it = us[idx[b]].begin(); it != us[idx[b]].end(); ++it) us[idx[a]].insert(*it);
  }  
}
ll cnt = -1;
void DFS(int v)
{
  C[v] = 0, idx[v] = -1;
  for(auto x : G[v])
  {
    DFS(x);
    C[v] += C[x];

    if(idx[v] == -1)
    {
      idx[v] = idx[x];
    }
    else merguj(v,x);
  }
  if(C[v] == 0)
  {
    C[v] = l, res += C[v]*w[v], ++cnt, su_us[cnt] = 0, idx[v] = cnt, us[cnt].clear();
  }
  else
  {
    us[idx[v]].insert({w[v],(ll)2e10}), su_us[idx[v]] += (ll)2e10;
    while(C[v] > r)
    {
      ll roz = C[v]-r;
      Element at = *us[idx[v]].begin();
      us[idx[v]].erase(us[idx[v]].find(at));
      if(at.su <= roz)
      {
        C[v] -= at.su, su_us[idx[v]] -= at.su, res += at.val*at.su;
      }
      else
      {
        C[v] -= roz, su_us[idx[v]] -= roz, res += at.val*roz;
        us[idx[v]].insert({at.val,at.su-roz});
      }
    }
    while(su_us[idx[v]] > C[v]-l)
    {
      ll roz = su_us[idx[v]]-(C[v]-l);
      Element at = *us[idx[v]].rbegin();
      us[idx[v]].erase(us[idx[v]].find(at));
      if(at.su <= roz)
      {
        su_us[idx[v]] -= at.su;
      }
      else
      {
        su_us[idx[v]] -= roz, us[idx[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, cnt=-1;
  DFS(0);

  return res;
}

• 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