Submission #1110995

#TimeUsernameProblemLanguageResultExecution timeMemory
1110995crafticatMagic Tree (CEOI19_magictree)C++17
55 / 100
114 ms37192 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> using V = vector<T>; using vi = V<int>; using vb = V<bool>; using pi = pair<int,int>; #define F0R(i,n) for (int i = 0; i < n;i++) #define FOR(i, j, n) for(int i = j; i < n;i++) #define ckmin(x,y) x = min(x,y) #define f first #define s second using ll = long long; constexpr int INF = 1e9 + 5; struct STL { vi pointers; V<multiset<pi>> gradients; STL(int n) { pointers.resize(n); gradients.resize(n); for (int i = 0; i < n;i++) { pointers[i] = i; } } void merge(int x, int y) { int pX = pointers[x], pY = pointers[y]; if (gradients[pY].size() > gradients[pX].size()) swap(pX,pY); pointers[y] = pX; pointers[x] = pX; for (auto elm : gradients[pY]) { gradients[pX].insert(elm); } } void insert(int x, int t, int v) { x = pointers[x]; int sum = 0; while (true) { auto it = gradients[x].upper_bound({t, INF}); if (it == gradients[x].end()) break; int t1 = it->first; sum += it->second; gradients[x].erase(it); if (sum > v) { sum -= v; gradients[x].insert({t1, sum}); break; } } gradients[x].insert({t,v}); } int query(int x) { x = pointers[x]; int sum = 0; for (auto [v,y] : gradients[x]) { sum += y; } return sum; } }; V<pi> dat; V<vi> g; STL *stl; void solve(int x, int p) { for (auto y : g[x]) { if (y == p) continue; solve(y, x); stl->merge(x, y); } stl->insert(x, dat[x].f, dat[x].s); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin >> n >> m >> k; g.resize(n + 1); stl = new STL(n + 1); FOR(i, 2, n + 1) { int p; cin >> p; g[p].push_back(i); g[i].push_back(p); } dat.resize(n + 1); F0R(i, m) { int v, t, p; cin >> v >> t >> p; dat[v] = {t, p}; } solve(1, -1); cout << stl->query(1); 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...