Submission #399371

#TimeUsernameProblemLanguageResultExecution timeMemory
39937112tqianWorst Reporter 4 (JOI21_worst_reporter4)C++17
14 / 100
84 ms4540 KiB
#include <bits/stdc++.h> using namespace std; #define f1r(i, a, b) for (int i = a; i < b; ++i) #define f0r(i, a) f1r(i, 0, a) #define each(t, a) for (auto& t : a) #define mp make_pair #define f first #define s second #define pb push_back #define eb emplace_back #define sz(x) (int)(x).size() #define all(x) begin(x), end(x) typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pi; typedef pair<ll, ll> pl; typedef vector<pi> vpi; typedef vector<pl> vpl; template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template <class T> int get_pos(vector<T> v, T x) { return lower_bound(all(v), x) - v.begin(); } const int N = 2e5 + 5; struct DSU { vi e; void init(int n) { e = vi(n, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return false; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; return true; } }; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vi a(n); vi h(n); vl c(n); vector<bool> vis(n); vector<bool> cyc(n); vi tmp; f0r(i, n) { cin >> a[i] >> h[i] >> c[i]; --a[i]; tmp.pb(h[i]); } sort(all(tmp)); tmp.erase(unique(all(tmp)), tmp.end()); if (n > 5002) return 0; f0r(i, n) h[i] = get_pos(tmp, h[i]); f0r(i, n) h[i] = sz(tmp) - 1 - h[i]; DSU D; D.init(n); f0r(i, n) { if (vis[i]) continue; int cur = i; vi path; while (!vis[cur]) { vis[cur] = true; path.pb(cur); cur = a[cur]; } int loc = -1; f0r(i, sz(path)) { if (path[i] == cur) { loc = i; break; } } if (loc == -1) continue; f1r(i, loc, sz(path)) { cyc[path[i]] = true; D.unite(cur, path[i]); } } vi v; f0r(i, n) v.pb(D.get(i)); sort(all(v)); v.erase(unique(all(v)), v.end()); vi id(n); f0r(i, n) id[i] = get_pos(v, D.get(i)); int sz = sz(v); vector<map<int, ll>> dp(sz); vector<vi> comps(sz); f0r(i, n) { comps[id[i]].pb(i); } vi roots; each(x, v) { if (cyc[comps[get_pos(v, x)][0]]) { roots.pb(get_pos(v, x)); } } vector<vi> g(sz); f0r(i, n) { int x = id[i]; int y = id[a[i]]; if (x == y) continue; g[x].pb(y); g[y].pb(x); } ll ans = 0; int cnt = 0; each(r, roots) { function<void(int, int)> dfs = [&](int u, int p) { each(v, g[u]) { if (v == p) continue; dfs(v, u); if (sz(dp[v]) > sz(dp[u])) swap(dp[u], dp[v]); each(x, dp[v]) { dp[u][x.f] += x.s; } } // add the root auto& st = dp[u]; if (u == r) { auto it = st.begin(); while (it != st.end()) { if (it != st.begin()) { it->s += prev(it)->s; } it = next(it); } map<int, ll> cost; each(vert, comps[u]) { cost[h[vert]] += c[vert]; } ll mx = 0; if (sz(st)) mx = st.rbegin()->s; each(vert, cost) { int d = vert.f; ll v = vert.s; it = st.upper_bound(d); if (it != st.begin()) { ckmax(mx, prev(it)->s + v); } ckmax(mx, v); } ans += mx; } else { int vert = comps[u][0]; int d = h[vert]; ll v = c[vert]; st[d] += v; auto it = st.upper_bound(d); while (it != st.end() && v) { ll rem = min(v, it->s); it->s -= rem; v -= rem; if (it->s == 0) { it = next(it); st.erase(prev(it)); } } } }; dfs(r, -1); } ll sum = 0; f0r(i, n) sum += c[i]; ans = sum - ans; cout << ans << '\n'; return 0; } /** * goes to a[i] * maximize the cost if decreasing subsequences up the tree * let's consider the cycle at the very end * then there is a cost associated with each possible value at the top * and a cost associated with nothing * first consider the case of fixed * things decrease from the root * this means that in increasing order it's better */

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:128:9: warning: unused variable 'cnt' [-Wunused-variable]
  128 |     int cnt = 0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...