Submission #1242530

#TimeUsernameProblemLanguageResultExecution timeMemory
1242530mychecksedadTree (IOI24_tree)C++20
41 / 100
2097 ms47604 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; #define vi vector<int> #define pb push_back #define pii pair<int,int> #define ff first #define ss second #define all(x) x.begin(),x.end() #define ll long long int const int N = 2e5+100; int n; vector<int> p, w; multiset<array<ll, 2>> S[N]; vi g[N]; ll dp[N], sum[N], extra[N]; ll L, R; void dfs(int v){ S[v].clear(); int big = -1; sum[v] = 0; extra[v] = 0; dp[v] = 0; for(int u: g[v]){ dfs(u); extra[v] += extra[u]; if(big == -1 || S[u].size() > S[big].size()) big = u; dp[v] += dp[u]; sum[v] += sum[u]; } if(big == -1){ sum[v] = L; dp[v] += L * w[v]; return; } S[v].swap(S[big]); for(int u: g[v]){ if(u != big) for(auto x: S[u]) S[v].insert(x); } if(sum[v] <= L){ dp[v] += (L-sum[v]) * w[v]; sum[v] = L; }else if(sum[v] <= R){ S[v].insert({w[v], sum[v] - L}); extra[v] += sum[v] - L; }else{ ll dif = sum[v] - R; while(dif && S[v].size()){ auto it = S[v].begin(); auto [W, P] = *it; if(W > w[v]) break; if(P <= dif){ extra[v] -= P; dp[v] += W * P; S[v].erase(it); dif -= P; }else{ extra[v] -= dif; dp[v] += dif * W; S[v].erase(it); S[v].insert({W, P - dif}); dif = 0; } } if(dif > 0){ dp[v] += w[v] * dif; } sum[v] = R; S[v].insert({w[v], R-L}); extra[v] += R-L; } ll max_extra = sum[v] - L; while(extra[v] > max_extra && S[v].size()){ auto it = prev(S[v].end()); auto [W, P] = *it; if(extra[v] - P >= max_extra){ S[v].erase(it); extra[v] -= P; }else{ S[v].erase(it); S[v].insert({W, P - (extra[v] - max_extra)}); extra[v] = max_extra; } } } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = (int)p.size(); for(int i = 1; i < n; ++i) g[P[i]].pb(i); } long long query(int l, int r) { L = l, R = r; dfs(0); return dp[0]; }
#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...