Submission #1200144

#TimeUsernameProblemLanguageResultExecution timeMemory
1200144HanksburgerMagic Tree (CEOI19_magictree)C++20
100 / 100
809 ms421712 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct node { node *lc, *rc; int l, r, add, set, sz; node(int l, int r) : lc(0), rc(0), l(l), r(r), add(0), set(-1), sz(1) {} }; int par[100005], day[100005], weight[100005], n, m, k; vector<pair<pair<int, int>, int> > vec; vector<int> child[100005]; void push(node* x) { if (x->l==x->r) return; int mid=(x->l+x->r)/2; if (!x->lc) x->lc=new node(x->l, mid); if (!x->rc) x->rc=new node(mid+1, x->r); if (x->set==-1) { if (x->lc->set==-1) x->lc->add+=x->add; else x->lc->set+=x->add; if (x->rc->set==-1) x->rc->add+=x->add; else x->rc->set+=x->add; } else { x->lc->add=0; x->lc->set=x->set; x->rc->add=0; x->rc->set=x->set; } x->add=0; x->set=-1; } void convert(node* x) { if (!x->lc && !x->rc) { if (x->set==-1) vec.push_back({{x->l, x->r}, x->add}); else vec.push_back({{x->l, x->r}, x->set}); return; } push(x); convert(x->lc); convert(x->rc); x->sz=x->lc->sz+x->rc->sz; } void add(node* x, int ql, int qr, int val) { if (ql<=x->l && x->r<=qr) { if (x->set==-1) x->add+=val; else x->set+=val; return; } push(x); int mid=(x->l+x->r)/2; if (x->l<=qr && ql<=mid) add(x->lc, ql, qr, val); if (mid<qr && ql<=x->r) add(x->rc, ql, qr, val); x->sz=x->lc->sz+x->rc->sz; } void Set(node* x, int ql, int qr, int val) { if (ql<=x->l && x->r<=qr) { x->add=0; x->set=val; return; } push(x); int mid=(x->l+x->r)/2; if (x->l<=qr && ql<=mid) Set(x->lc, ql, qr, val); if (mid<qr && ql<=x->r) Set(x->rc, ql, qr, val); x->sz=x->lc->sz+x->rc->sz; } int query(node* x, int ind) { if (!x->lc && !x->rc) { if (x->set==-1) return x->add; return x->set; } push(x); int mid=(x->l+x->r)/2; if (ind<=mid) return query(x->lc, ind); return query(x->rc, ind); } node* combine(node* x, node* y) { if (x->sz>y->sz) swap(x, y); vec.clear(); convert(x); for (int i=0; i<vec.size(); i++) add(y, vec[i].first.first, vec[i].first.second, vec[i].second); return y; } node* dfs(int u) { node* x=new node(1, k); for (int v:child[u]) x=combine(x, dfs(v)); if (day[u]) { int res=query(x, day[u])+weight[u], l=day[u], r=k; while (l<r) { int mid=(l+r+1)/2; if (query(x, mid)<=res) l=mid; else r=mid-1; } Set(x, day[u], l, res); } return x; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> k; for (int i=2; i<=n; i++) { cin >> par[i]; child[par[i]].push_back(i); } for (int i=1; i<=m; i++) { int x, y, z; cin >> x >> y >> z; day[x]=y, weight[x]=z; } node* x=dfs(1); cout << query(x, k); }
#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...