Submission #1231607

#TimeUsernameProblemLanguageResultExecution timeMemory
1231607banganTree (IOI24_tree)C++20
0 / 100
2097 ms44176 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long const int N = 200200; int n; std::vector<int> w, p; vector<int> adj[N]; ll res; ll sum[N]; vector<int> dfs(int v, ll l, ll r) { if (adj[v].empty()) { sum[v] = l; res += l; return {v}; } vector<int> sub{v}; sum[v]=0; for (int u : adj[v]) { auto vec = dfs(u, l, r); sum[v] += sum[u]; for (int x : vec) sub.pb(x); } if (sum[v] <= r) return sub; sort(sub.begin(), sub.end(), [&](int i, int j) { return w[i] > w[j]; }); while (sum[v] != r) { int x = sub.back(); sub.pop_back(); int save_x = x; ll mn = sum[v] - r; while (x != v) { mn = min(mn, sum[x] - l); x = p[x]; } x = save_x; res += mn * w[x]; while (x != v) { sum[x] -= mn; x = p[x]; } assert(v==x); sum[x] -= mn; } return sub; } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = W.size(); for (int i=1; i<n; i++) adj[P[i]].pb(i); } long long query(int L, int R) { res = 0; dfs(0, L, R); return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...