제출 #1110996

#제출 시각아이디문제언어결과실행 시간메모리
1110996crafticatMagic Tree (CEOI19_magictree)C++17
100 / 100
137 ms47776 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> using V = vector<T>; using ll = long long; using vi = V<ll>; using vb = V<bool>; using pi = pair<ll,ll>; #define F0R(i,n) for (ll i = 0; i < n;i++) #define FOR(i, j, n) for(ll i = j; i < n;i++) #define ckmin(x,y) x = min(x,y) #define f first #define s second constexpr ll INF = 1e18 + 5; struct STL { vi pollers; V<multiset<pi>> gradients; STL(ll n) { pollers.resize(n); gradients.resize(n); for (ll i = 0; i < n;i++) { pollers[i] = i; } } void merge(ll x, ll y) { ll pX = pollers[x], pY = pollers[y]; if (gradients[pY].size() > gradients[pX].size()) swap(pX,pY); pollers[y] = pX; pollers[x] = pX; for (auto elm : gradients[pY]) { gradients[pX].insert(elm); } } void insert(ll x, ll t, ll v) { x = pollers[x]; ll sum = 0; while (true) { auto it = gradients[x].upper_bound({t, INF}); if (it == gradients[x].end()) break; ll 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}); } ll query(ll x) { x = pollers[x]; ll sum = 0; for (auto [v,y] : gradients[x]) { sum += y; } return sum; } }; V<pi> dat; V<vi> g; STL *stl; void solve(ll x, ll 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); ll n, m, k; cin >> n >> m >> k; g.resize(n + 1); stl = new STL(n + 1); FOR(i, 2, n + 1) { ll p; cin >> p; g[p].push_back(i); g[i].push_back(p); } dat.resize(n + 1); F0R(i, m) { ll 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...