Submission #519763

#TimeUsernameProblemLanguageResultExecution timeMemory
519763MonarchuwuMagic Tree (CEOI19_magictree)C++17
100 / 100
158 ms37712 KiB
#include<iostream> #include<algorithm> #include<vector> #include<map> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define ff first #define ss second const int N = 1e5 + 9; int n, m, k; int p[N]; pii fruit[N]; vector<int> g[N]; map<int, ll> dp[N]; namespace sub8 { int cnt(0), b[N]; void dfs(int u) { for (int v : g[u]) { dfs(v); if (dp[u].size() < dp[v].size()) dp[u].swap(dp[v]); for (auto it : dp[v]) dp[u][it.ff] += it.ss; } if (fruit[u].ff) { dp[u][fruit[u].ff] += fruit[u].ss; map<int, ll>::iterator it = dp[u].upper_bound(fruit[u].ff), tmp; for (ll diff = 0; it != dp[u].end(); it = tmp) { diff += it->ss; if (diff <= fruit[u].ss) { // set dp[u][it->ff] = dp[u][fruit[u].ff], reset diff = 0 tmp = next(it); dp[u].erase(it); } else { // nothing change, recalc diff it->ss = diff - fruit[u].ss; break; } } } } void solve() { for (int i = 1; i <= n; ++i) if (fruit[i].ff) b[++cnt] = fruit[i].ff; sort(b + 1, b + cnt + 1); cnt = unique(b + 1, b + cnt + 1) - b; for (int i = 1; i <= n; ++i) if (fruit[i].ff) fruit[i].ff = lower_bound(b + 1, b + cnt, fruit[i].ff) - b; dfs(1); ll ans(0); for (auto it : dp[1]) ans += it.ss; cout << ans << '\n'; } } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> m >> k; for (int i = 2; i <= n; ++i) { cin >> p[i]; g[p[i]].push_back(i); } for (int i = 0, v; i < m; ++i) { cin >> v; cin >> fruit[v].ff >> fruit[v].ss; } sub8::solve(); } /** /\_/\ * (= ._.) * / >0 \>1 **/
#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...