Submission #1232336

#TimeUsernameProblemLanguageResultExecution timeMemory
1232336banganTree (IOI24_tree)C++20
0 / 100
39 ms8260 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long const int N = 60'000 + 4; int n; vector<int> p, w; vector<int> adj[N]; ll ans; ll dfs(int v, ll l, ll r) { if (adj[v].empty()) { ans += l * w[v]; return l; } ll sum = 0; for (int u : adj[v]) sum += dfs(u, l, r); if (v==0 || w[p[v]] <= w[v]) { ll t = max(0ll, sum - r); ans += t * w[v]; sum -= t; return sum; } else { ll t = sum - l; ans += t * w[v]; sum -= t; return sum; } } void init(std::vector<int> P, std::vector<int> W) { n = P.size(); p = P; w = W; for (int i=1; i<n; i++) adj[p[i]].pb(i); } long long query(int L, int R) { ans = 0; dfs(0, L, R); 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...