Submission #1187988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187988		nikd	Tree (IOI24_tree)	C++20	10 / 100	2095 ms	22944 KiB

tree

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

int n;
vector<vector<int>> adj;
vector<ll> w;

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

long long query(int L, int R) {
  ll r = R; ll l = L;
  ll sol = 0;
  function<ll(int)> dfs = [&](int v)->ll{
    if(!adj[v].size()){
        sol += w[v]*l;
        return l;
    }
    ll sz = 0;
    for(int u: adj[v]){
        sz += dfs(u);
    }
    if(sz <= r) return sz;
    sol += (sz-r)*w[v];
    return r;
  };
  dfs(0);
  return sol;
}

• 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