Submission #386559

#TimeUsernameProblemLanguageResultExecution timeMemory
386559PurpleCrayonEvent Hopping 2 (JOI21_event2)C++17
0 / 100
11 ms16108 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define sz(v) int(v.size()) typedef long long ll; const int MAXN = 2e5+10; const ll INF = 1e18+10; int n, p[MAXN], a[MAXN], loc[MAXN]; ll co[MAXN]; vector<int> adj[MAXN]; struct T { int tl, tr; T *l=nullptr, *r=nullptr; ll lzy_ad, lzy_mx; T(int _tl, int _tr): tl(_tl), tr(_tr) { lzy_ad = 0, lzy_mx = -INF; } void extend(){ if (l||r||tl==tr) return; int tm=(tl+tr)/2; l = new T(tl, tm), r = new T(tm+1, tr); } void prop(){ l->lzy_ad += lzy_ad, r->lzy_ad += lzy_ad; l->lzy_mx = max(lzy_mx, l->lzy_mx + lzy_ad); r->lzy_mx = max(lzy_mx, r->lzy_mx + lzy_ad); lzy_mx = -INF, lzy_ad = 0; } void add(int ql, int qr, ll v) { if (qr < tl || ql > tr) return; if (ql <= tl && tr <= qr) { lzy_ad += v; lzy_mx += v; return; } extend(), prop(); l->add(ql, qr, v), r->add(ql, qr, v); } void smax(int ql, int qr, ll v) { if (qr < tl || ql > tr) return; if (ql <= tl && tr <= qr) { lzy_mx = max(lzy_mx, v); return; } extend(), prop(); l->smax(ql, qr, v), r->smax(ql, qr, v); } ll qry(int pos) { if (tl == tr) return max(lzy_ad, lzy_mx); extend(), prop(); if (pos <= l->tr) return l->qry(pos); else return r->qry(pos); } }; struct S { map<int, int> mp; T *t; void init() { t = new T(0, n-1); } ll get(int v){ return t->qry(v); } void merge(S& nxt){ nxt.mp[n-1]++; for (auto it = nxt.mp.begin(), prv = it; it != nxt.mp.end(); prv = it, it = next(it)) { int p=-1, c=it->first; if (it != nxt.mp.begin()) p = prv->first; t->add(p+1, c, nxt.t->qry(c)); mp[c]++; } map<int, int>().swap(nxt.mp); } void upd(int v, ll amt){ mp[v]++; t->smax(0, v, amt); } } sub[MAXN]; void dfs(int c=0){ sub[loc[c]].init(); for (auto nxt : adj[c]) { dfs(nxt); if (sz(sub[loc[c]].mp) < sz(sub[loc[nxt]].mp)) swap(loc[c], loc[nxt]); sub[loc[c]].merge(sub[loc[nxt]]); } sub[loc[c]].upd(a[c], co[c]+sub[loc[c]].get(a[c])); } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) { cin >> p[i] >> a[i] >> co[i], --p[i]; if (i) adj[p[i]].push_back(i); } { map<ll, int> mp; int cc=0; for (int i = 0; i < n; i++) mp[a[i]]++; for (auto& v : mp) v.second=cc++; for (int i = 0; i < n; i++) a[i] = mp[a[i]]; } iota(loc, loc+n, 0); dfs(); ll ans = 0; for (int i = 0; i < n; i++) ans = max(ans, sub[loc[0]].get(i)); ans = accumulate(co, co+n, 0ll) - ans; 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...