Submission #1232215

#TimeUsernameProblemLanguageResultExecution timeMemory
1232215banganTree (IOI24_tree)C++20
18 / 100
68 ms23968 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; vector<int> p, w; vector<int> adj[N]; ll cache; ll c[N]; vector<ll> roots; vector<ll> suf; void dfs(int v) { if (adj[v].empty()) cache += w[v], c[v] = 1; for (int u : adj[v]) { dfs(u); c[v] += c[u]; } if (w[v]==0) c[v] = 1; if (v==0 || w[p[v]]==0) roots.pb(c[v]); } 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); dfs(0); sort(roots.begin(), roots.end()); suf = roots; for (int i = int(suf.size()) - 2; 0 <= i; i--) suf[i] += suf[i+1]; } long long query(int L, int R) { ll ans = cache * L; ll k = (R + L-1) / L; int i = lower_bound(roots.begin(), roots.end(), k) - roots.begin(); if (i != roots.size()) ans += 1ll * L * suf[i] - 1ll * R * (roots.size() - i); 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...