Submission #1231615

#TimeUsernameProblemLanguageResultExecution timeMemory
1231615banganTree (IOI24_tree)C++20
0 / 100
2095 ms35704 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long #define X first #define Y second #define pii pair<int, int> const int N = 200200; int n; std::vector<int> w, p; vector<int> adj[N]; int sz[N]; int imp[N]; void prep(int v) { sz[v]=1; imp[v] = -1; for (int u : adj[v]) { prep(u); sz[v] += sz[u]; if (imp[v] == -1 || sz[imp[v]] < sz[u]) imp[v] = u; } } priority_queue<pii> pq; ll res; ll sum[N]; void add(int v, int l, int r) { pq.push({-w[v], v}); for (int u : adj[v]) add(u, l, r); } void dfs(int v, ll l, ll r) { sum[v]=0; if (adj[v].empty()) { sum[v] = l; res += l; pq.push({-w[v], v}); return; } for (int u : adj[v]) if (u != imp[v]) { dfs(u, l, r); sum[v] += sum[u]; while (!pq.empty()) pq.pop(); } { dfs(imp[v], l, r); sum[v] += sum[imp[v]]; } for (int u : adj[v]) if (u != imp[v]) add(u, l, r); pq.push({-w[v], v}); if (sum[v] <= r) return; vector<int> late; while (sum[v] != r) { int x = pq.top().Y; late.pb(x); pq.pop(); 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; } for (int x : late) pq.push({-w[x], x}); } 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); prep(0); } long long query(int L, int R) { res = 0; while (!pq.empty()) pq.pop(); 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...