Submission #1177230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177230		madamadam3	Tree (IOI24_tree)	C++20	10 / 100	2096 ms	27040 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

void init(vector<int> P, vector<int> W) {
  p = P;
  w = W;
  n = (int)p.size();

  adj.assign(n, vector<int>());
  for (int i = 1; i < n; i++) adj[P[i]].push_back(i), adj[i].push_back(P[i]);
  curval.assign(n, 0LL);
}

ll dfs(int u, int p, int L, int R) {
  int children = 0;
  ll childsum = 0;

  for (int v : adj[u]) {
    if (v == p) continue;
    children++;

    childsum += dfs(v, u, L, R);
  }

  if (children == 0) {
    return curval[u] = L;
  } else {
    if (childsum > R) {
      curval[u] = R - childsum;
      return R;
    } else if (childsum < L) {
      curval[u] = L - childsum;
      return L;
    } else {
      curval[u] = 0;
      return childsum;
    }
  }
}

ll query(int L, int R) {
  curval.assign(n, 0LL);
  dfs(0, -1, L, R);

  ll tc = 0;
  for (int i = 0; i < n; i++) tc += abs(curval[i]) * w[i];

  return tc;
}

• 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