Submission #1242762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242762		SalihSahin	Tree (IOI24_tree)	C++20	0 / 100	111 ms	37888 KiB

tree

#include "bits/stdc++.h"
#include "tree.h"
using namespace std;
#define pb push_back

const int inf = 1e9 + 5;

struct SEGT{
  vector<int> tree;

  void init(int n){
    tree.assign(4*n, 0);
  }

  void update(int ind, int l, int r, int pos, int val){
    if(l == r){
      tree[ind] += val;
    }
    else{
      int m = (l + r)/2;

      if(pos <= m) update(ind*2, l, m, pos, val);
      else update(ind*2+1, m+1, r, pos, val);

      tree[ind] = (tree[ind*2] + tree[ind*2+1]);
    }
  }

  int query(int ind, int l, int r, int ql, int qr){
    if(l > r || ql > qr || l > qr || r < ql) return 0;
    if(l >= ql && r <= qr){
      return tree[ind];
    }
    else{
      int m = (l + r)/2;

      return (query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr));
    }
  }
};

SEGT seg;

int n;
vector<long long> p, w, act, ansarr, in, out;
vector<vector<int> > ch;
int leaf, tmr;
long long cur;

void dfs(int node, long long premn){
  in[node] = ++tmr;
  if(!ch[node].size()){
     leaf++;
     cur += w[node];
     seg.update(1, 1, n, in[node], 1);
  }
  else if(node < premn){
    act[node] = 1;
  }

  for(auto itr: ch[node]){
    dfs(itr, min(premn, w[node]));
  }
  out[node] = tmr;
}

void init(vector<int> P, vector<int> W) {
  n = (int)P.size();
  p.resize(n);
  w.resize(n);
  act.assign(n, 0);
  ansarr.assign(n+2, inf);
  seg.init(n);
  tmr = 0;
  in.resize(n);
  out.resize(n);

  leaf = 0;
  for(int i = 0; i < n; i++){
    w[i] = W[i];
    p[i] = P[i];
  }

  ch.resize(n);
  for(int i = 1; i < n; i++){
    ch[p[i]].pb(i);
  }
  dfs(0, inf);
  ansarr[n] = cur;

  set<array<long long, 3> > st;
  for(int i = 0; i < n; i++){
    if(act[i]){
      int x = seg.query(1, 1, n, in[i], out[i]);
      st.insert({w[i], x, i});
    }
  }

  int root = leaf;
  for(int i = n-1; i >= 1; i--){
    if(leaf <= i){
      ansarr[i] = cur;
      continue;
    }

    while(true){
      if(!st.size()){
        cout<<"stupid"<<endl;
        abort();
      }

      auto itr = *st.begin();
      int x = seg.query(1, 1, n, in[i], out[i]);
      if(!x){
        st.erase(st.find(itr));
        continue;
      }

      cur += itr[0];
      seg.update(1, 1, n, in[itr[2]], -1);
      array<long long, 3> nxt = itr;
      nxt[1]--;
      st.erase(st.find(itr));
      if(nxt[1] >= 0) st.insert(nxt);
      break;
    }

    ansarr[i] = cur;
  }
}

long long query(int L, int R){
  if(R >= n){
    return ansarr[n];
  }
  else{
    return ansarr[R];
  }
}

• 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