Submission #1199056

#TimeUsernameProblemLanguageResultExecution timeMemory
1199056sofapudenMagic Tree (CEOI19_magictree)C++20
100 / 100
101 ms35400 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> d, w; vector<vector<int>> gr; vector<map<ll, ll>> chn; void f(int node) { auto &ret = chn[node]; for(auto y : gr[node]){ f(y); if(ret.size() < chn[y].size())swap(ret, chn[y]); for(auto x : chn[y])ret[x.first] += x.second; } if(w[node])ret[d[node]] += w[node]; ll am = w[node]; while(am) { auto z = ret.upper_bound(d[node]); if(z == ret.end())break; ll mn = min(am, z->second); z->second -= mn; am -= mn; if(!z->second)ret.erase(z); } } int main () { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; gr.resize(n); d.resize(n, 0); w.resize(n, 0); chn.resize(n); for(int i = 1; i < n; ++i){ int p; cin >> p; p--; gr[p].push_back(i); } for(int i = 0; i < m; ++i){ int a, b, c; cin >> a >> b >> c; a--; d[a] = b; w[a] = c; } f(0); ll ans = 0; for(auto x : chn[0])ans += x.second; cout << ans << '\n'; }
#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...