Submission #1215693

#TimeUsernameProblemLanguageResultExecution timeMemory
1215693onbertWorst Reporter 4 (JOI21_worst_reporter4)C++20
0 / 100
7 ms14404 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 5, INF = 1e10; int n; vector<int> adj[maxn]; int a[maxn], c[maxn]; int dsu[maxn]; multiset<pair<int,int>> s[maxn]; int rt(int u) { if (dsu[u] == u) return u; return dsu[u] = rt(dsu[u]); } void merge(int u, int v) { u = rt(u), v = rt(v); if (s[u].size() > s[v].size()) swap(u, v); dsu[u] = v; for (auto [x, y]:s[u]) s[v].insert({x, y}); while (s[u].size()) s[u].erase(s[u].begin()); } void dfs(int u) { for (int v:adj[u]) { dfs(v); merge(u, v); } int U = rt(u); if (s[U].size() && s[U].begin()->first <= a[u]) { pair<int,int> cur = *prev(s[U].lower_bound({a[u], -INF})); s[U].erase(s[U].find(cur)); s[U].insert({cur.first, cur.second - c[u]}); } s[U].insert({a[u], c[u]}); // cout << u << endl; // for (auto [x, y]:s[U]) cout << x << " " << y << endl; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; int all = 0; for (int i=1;i<=n;i++) { int p; cin >> p >> a[i] >> c[i]; if (i != 1) adj[p].push_back(i); all += c[i]; } for (int i=1;i<=n;i++) dsu[i] = i; dfs(1); vector<int> vec; for (auto [x, y]:s[rt(1)]) vec.push_back(y); reverse(vec.begin(), vec.end()); int ans = 0, cur = 0; for (auto i:vec) { cur += i; ans = max(cur, ans); } cout << all - ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...