Submission #1210469

#TimeUsernameProblemLanguageResultExecution timeMemory
1210469PagodePaivaTree (IOI24_tree)C++20
10 / 100
2096 ms27044 KiB
#include "tree.h" #include<bits/stdc++.h> using namespace std; const int N = 200010; int n; vector <int> g[N]; long long c[N]; long long sz[N]; long long l, r; long long ans = 0; void dfs(int v, int p){ sz[v] = 0; for(auto x : g[v]){ if(x == p) continue; dfs(x, v); sz[v] += sz[x]; } if(sz[v] < l){ ans += (l-sz[v])*c[v]; sz[v] = l; } else if(sz[v] > r){ ans += (sz[v]-r)*c[v]; sz[v] = r; } return; } void init(std::vector<int> P, std::vector<int> W) { n = (int)P.size(); for(int i = 1;i < n;i++){ g[P[i]].push_back(i); g[i].push_back(P[i]); } for(int i = 0;i < n;i++){ c[i] = W[i]; } return; } long long query(int L, int R) { l = L; r = R; ans = 0; dfs(0, 0); return ans; }
#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...