제출 #1242067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242067		SalihSahin	트리 (IOI24_tree)	C++20	0 / 100	2142 ms	1685336 KiB

tree

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


int n;
vector<long long> p, w, order;
vector<vector<int> > ch;

void dfs(int node){
  for(auto itr: ch[node]){
    dfs(itr);
  }
  order.pb(node);
}

void init(vector<int> P, vector<int> W) {
  n = (int)P.size();
  p.resize(n);
  w.resize(n);
  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);
}

long long query(int L, int R){
  vector<long long> c(n), sub(n);
  set<pair<long long, long long> > relax[n];

  for(int i = 0; i < n; i++){
    int node = order[i];

    if(!ch[node].size()){
      c[node] = L; // leafler L olacak kalanlar <= 0
      sub[node] = L;
      continue;
    }

    for(auto itr: ch[node]){
      sub[node] += sub[itr];
      for(auto j: relax[itr]){
        relax[node].insert(j);
      }
    }
    relax[node].insert({w[node], node});

    while(sub[node] > R){
       auto best = *relax[node].begin();

       long long cnt = sub[best.second] - L;
       cnt = min(cnt, sub[node] - R);

       c[best.second] -= cnt;
       sub[best.second] -= cnt;

       int up = best.second;
       while(up != node){
         up = p[up];
         sub[up] -= cnt;
       }

       if(sub[best.second] == L){
          relax[node].erase(relax[node].find(best));
       }
    }
  }

  long long ans = 0;
  for(int i = 0; i < n; i++){
    ans += abs(c[i]) * w[i];
  }
  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