Submission #1242085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242085		SalihSahin	Tree (IOI24_tree)	C++20	23 / 100	2095 ms	78080 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;
    }

    int mxc = ch[node][0], mxsz = 0;
    for(auto itr: ch[node]){
      sub[node] += sub[itr];

      if(relax[itr].size() > mxsz){
        mxc = itr;
        mxsz = relax[itr].size();
      }
    }
    swap(relax[node], relax[mxc]);
    for(auto itr: ch[node]){
      if(itr == mxc) continue;
      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);
       int up = best.second;
       while(up != node){
         up = p[up];
         cnt = min(cnt, sub[up] - L);
         if(cnt == 0) break;
       }

       if(!cnt){
        relax[node].erase(relax[node].find(best));
        continue;
       }

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

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

  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: 10 / 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