Submission #1245533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245533		franuch	Tree (IOI24_tree)	C++20	10 / 100	2096 ms	28292 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e18;

ll V;
vc<ll> par, wgh;
vc<vc<ll>> g;

void init(vc<int> P, vc<int> W) {
  par.assign(all(P));
  wgh.assign(all(W));
  V = sz(par);
  g.assign(V, vc<ll>());
  for (ll v = 1; v < V; v++)
          g[par[v]].pub(v);
}

ll query(int _L, int _R) {
        ll L = _L;
        ll R = _R;
        vc<ll> dp(V, 0);
        ll ret = 0;
        function<void(ll)> dfs = [&](ll v) {
                ll sum = 0;
                for (ll w : g[v]) {
                        dfs(w);
                        sum += dp[w];
                }
                ll l = L - sum, r = R - sum;
                ll x;
                if (r < 0)
                        x = r;
                else if (0 < l)
                        x = l;
                else
                        x = 0;
                ret += abs(x) * wgh[v];
                dp[v] = sum + x;
        };
        dfs(0);
        return ret;
}

• 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