Submission #1214508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214508		hyakup	Tree (IOI24_tree)	C++20	10 / 100	2095 ms	28136 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n;
vector<int> p, w;
vector<vector<int>> adj;

void init(vector<int> P, vector<int> W) {
  p = P;
  n = (int)p.size();
  w = W;
  adj.resize(n);
  for( int i = 1; i < n; i++ ){
    adj[p[i]].push_back(i);
  }
}

ll query(int l, int r) {
  vector<ll> c(n), sum(n);

  function<void(int)> dfs = [&]( int cur ){
    for( int viz : adj[cur] ){
      dfs( viz );
      sum[cur] += sum[viz];
    }

    if( sum[cur] < l ){
      c[cur] = 1LL*l - sum[cur];
      sum[cur] = l;
    }
    if( sum[cur] > r ){
      c[cur] = 1LL*r - sum[cur];
      sum[cur] = r;
    }
  };

  dfs( 0 );

  ll resp = 0;
  for( int i = 0; i < n; i++ ) resp += 1LL*abs(c[i])*w[i];
  return resp;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 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