Submission #655972

#TimeUsernameProblemLanguageResultExecution timeMemory
655972lunchbox1Magic Tree (CEOI19_magictree)C++17
100 / 100
279 ms40248 KiB
/* Magic Tree https://oj.uz/problem/view/CEOI19_magictree */ #include <bits/stdc++.h> using namespace std; const int N = 1e5; int main() { ios::sync_with_stdio(0), cin.tie(0); int n, m, k; cin >> n >> m >> k; static int p[N]; for (int i = 1; i < n; i++) cin >> p[i], p[i]--; static pair<int, int> e[N]; while (m--) { int i, d, w; cin >> i >> d >> w, i--; e[i] = {d, w}; } static map<int, long long> f[N]; for (int i = n - 1; i > 0; i--) { if (e[i] != make_pair(0, 0)) { auto [d, w] = e[i]; f[i][d] += w; auto it = f[i].upper_bound(d); while (w > 0 && it != f[i].end()) { long long u = min((long long) w, it->second); w -= u, it->second -= u, ++it; } } int j = p[i]; if (f[i].size() > f[j].size()) swap(f[i], f[j]); for (auto [k, v] : f[i]) f[j][k] += v; } long long ans = 0; for (auto [k, v] : f[0]) ans += v; cout << ans << '\n'; 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...