Submission #954492

#TimeUsernameProblemLanguageResultExecution timeMemory
954492SkywkMagic Tree (CEOI19_magictree)C++17
100 / 100
102 ms38484 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e5; struct Tree{ vector<int> adj[MAXN + 1]; int ds[MAXN + 1], js[MAXN + 1]; void insert(map<int, long long>* dp, int v){ (*dp)[ds[v]] += js[v]; auto ptr = dp->find(ds[v]); int j_left = js[v]; while(j_left > 0 && next(ptr) != dp->end()){ auto nxt_ptr = next(ptr); if(nxt_ptr->second > j_left){ nxt_ptr->second -= j_left; break; } else{ j_left -= nxt_ptr->second; dp->erase(nxt_ptr); } } } map<int, long long>* TreeDp(int v){ auto curr_map = new map<int, long long>(); for(auto u : adj[v]){ auto new_map = TreeDp(u); if(new_map->size() > curr_map->size()) swap(curr_map, new_map); for(auto [key, value] : *new_map){ (*curr_map)[key] += value; } } if(ds[v] > 0) insert(curr_map, v); return curr_map; } }; Tree T; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M, K; cin>> N>> M>> K; for(int i=2; i<=N; i++){ int p; cin>> p; T.adj[p].push_back(i); } for(int i=0; i<M; i++){ int v; cin>> v; cin>> T.ds[v]>> T.js[v]; } auto dp = T.TreeDp(1); long long res = 0; for(auto [key, value] : *dp){ res += value; } cout<< res; return 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...