Submission #1214766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214766		madamadam3	Tree (IOI24_tree)	C++20	0 / 100	2095 ms	27296 KiB

tree

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

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
typedef long long ll;

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define each(a, x) for (auto &a : x)
#define FOR(i, a, b) for (int i = a; i < b; i++)

int n, l, r;
vi par, weight;
vvi adj;

int dfs(int u, int p, int &total_cost) {
  if (sz(adj[u]) == 1) {
    total_cost += l * weight[u];
    return l;
  }
  
  int child_sum = 0;
  each(v, adj[u]) {
    if (v == p) continue;

    child_sum += dfs(v, u, total_cost);
  }

  int my_sum = 0;
  if (par[u] == -1 || weight[par[u]] <= weight[u]) {
    my_sum = r - child_sum;
  } else {
    my_sum = l - child_sum;
  }

  total_cost += abs(my_sum) * weight[u];
  return child_sum + my_sum;
}

void init(vi P, vi W) {
  par = P; weight = W;
  n = sz(par);

  adj.assign(n, vi());
  FOR(i, 1, n) {
    adj[i].pb(par[i]);
    adj[par[i]].pb(i);
  }
}

ll query(int L, int R) {
  l = L; r = R;
  int total_cost = 0; dfs(0, -1, total_cost);
  return total_cost;
}

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