Submission #1206610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206610		HappyCapybara	Tree (IOI24_tree)	C++20	10 / 100	2096 ms	23456 KiB

tree

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

#define ll long long

int n, l, r;
vector<int> w;
vector<ll> st, c;
vector<vector<int>> g;

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

void dfs(int cur){
  for (int next : g[cur]){
    dfs(next);
    st[cur] += st[next];
  }
  if (st[cur] < l){
    c[cur] = l-st[cur];
    st[cur] = l;
  }
  if (st[cur] > r){
    c[cur] = r-st[cur];
    st[cur] = r;
  }
}

ll query(int L, int R){
  l = L;
  r = R;
  c.assign(n, 0);
  st.assign(n, 0);
  dfs(0);
  ll res = 0;
  for (int i=0; i<n; i++) res += (ll)w[i]*abs(c[i]);
  return res;
}

• 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