Submission #674961

#TimeUsernameProblemLanguageResultExecution timeMemory
674961skittles1412Worst Reporter 4 (JOI21_worst_reporter4)C++17
100 / 100
839 ms128984 KiB
#include "bits/extc++.h" using namespace std; template <typename T> void dbgh(const T& t) { cerr << t << endl; } template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t << " | "; dbgh(u...); } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \ << ": "; \ dbgh(__VA_ARGS__) #else #define cerr \ if (false) \ cerr #define dbg(...) #endif #define endl "\n" #define long int64_t #define sz(x) int(std::size(x)) constexpr int maxn = 2e5 + 5; struct DS { struct Node { long v, lazy; int lc, rc; }; inline static int heap_ptr = 1; inline static Node heap[1 << 25] {}; static int alloc() { return heap_ptr++; } static void alloc(int& o) { if (!o) { o = alloc(); } } static void maintain(int o) { auto& [v, lazy, lc, rc] = heap[o]; v = min(heap[lc].v, heap[rc].v) + lazy; } static void merge(int& a, int& b, int l, int r) { if (!b) { return; } else if (!a) { a = b; return; } auto& [v, lazy, lc, rc] = heap[a]; int mid = (l + r) / 2; lazy += heap[b].lazy; merge(lc, heap[b].lc, l, mid); merge(rc, heap[b].rc, mid + 1, r); maintain(a); } friend void merge(DS& a, DS& b) { merge(a.root, b.root, 0, maxn); } static long get(int o, int l, int r, int ind) { if (!o) { return 0; } auto& [v, lazy, lc, rc] = heap[o]; if (l == r) { return v; } int mid = (l + r) / 2; if (ind <= mid) { return lazy + get(lc, l, mid, ind); } else { return lazy + get(rc, mid + 1, r, ind); } } static void upd_add(int& o, long x) { alloc(o); heap[o].lazy += x; maintain(o); } static long query_min(int o, int l, int r, int ql, int qr) { if (!o) { return 0; } auto& [v, lazy, lc, rc] = heap[o]; if (ql <= l && r <= qr) { return v; } int mid = (l + r) / 2; long ans = 1e18; if (ql <= mid) { ans = min(ans, query_min(lc, l, mid, ql, qr)); } if (mid < qr) { ans = min(ans, query_min(rc, mid + 1, r, ql, qr)); } return ans + lazy; } static void upd_set(int& o, int l, int r, int ql, int qr, long x) { alloc(o); auto& [v, lazy, lc, rc] = heap[o]; if (ql <= l && r <= qr) { lc = rc = 0; v = lazy = x; return; } int mid = (l + r) / 2; x -= lazy; if (ql <= mid) { upd_set(lc, l, mid, ql, qr, x); } if (mid < qr) { upd_set(rc, mid + 1, r, ql, qr, x); } maintain(o); } int root = 0; long get(int ind) const { return get(root, 0, maxn, ind); } void upd_add(long x) { upd_add(root, x); } long query_min(int l, int r) const { return query_min(root, 0, maxn, l, r); } void upd_set(int l, int r, long x) { upd_set(root, 0, maxn, l, r, x); } void upd_min(int qr, long x) { int l = 0, r = qr + 1; while (l < r) { int mid = (l + r) / 2; if (query_min(mid, qr) >= x) { r = mid; } else { l = mid + 1; } } if (l <= qr) { upd_set(l, qr, x); } } }; bool vis[maxn], in_cyc[maxn]; int arr[maxn], cost[maxn]; vector<int> graph[maxn]; DS dp(int u, int p = -1) { vis[u] = true; DS cur; for (auto& v : graph[u]) { if (v == p || in_cyc[v]) { continue; } auto&& ndp = dp(v, u); merge(cur, ndp); } long cans = cur.get(arr[u]); cur.upd_add(cost[u]); if (p != -1) { cur.upd_min(arr[u], cans); } return cur; } void solve() { int n; cin >> n; int par[n]; for (int i = 0; i < n; i++) { cin >> par[i] >> arr[i] >> cost[i]; par[i]--; } for (int i = 0; i < n; i++) { graph[par[i]].push_back(i); } vector<int> comp(arr, arr + n); sort(begin(comp), end(comp)); comp.erase(unique(begin(comp), end(comp)), comp.end()); for (int i = 0; i < n; i++) { arr[i] = int(lower_bound(begin(comp), end(comp), arr[i]) - comp.begin()); } long ans = 0; for (int i = 0; i < n; i++) { if (vis[i]) { continue; } int u = i; vector<int> st; do { vis[u] = true; st.push_back(u); u = par[u]; } while (!vis[u]); vector<int> cyc(find(begin(st), end(st), u), st.end()); for (auto& a : cyc) { in_cyc[a] = true; } DS cds; map<int, long> ccost; for (auto& a : cyc) { ccost[arr[a]] += cost[a]; auto&& xans = dp(a); dbg(a, xans.get(1)); merge(cds, xans); } long cans = cds.get(0); for (auto& [k, v] : ccost) { dbg(k, v, cds.get(k)); cans = min(cans, cds.get(k) - v); } dbg(i, cans); ans += cans; } cout << ans << endl; } int main() { cin.tie(nullptr); cin.exceptions(ios::failbit); ios_base::sync_with_stdio(false); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...