제출 #993912

#제출 시각아이디문제언어결과실행 시간메모리
993912cadmiumskyWorst Reporter 4 (JOI21_worst_reporter4)C++17
100 / 100
488 ms76836 KiB
// o sa ia zero -- am avut dreptate // ia si de data asta zero #include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 2e5 + 5; const int inf = 1e9 + 5 + 7 + 9; vector<int> g[nmax]; int father[nmax], cost[nmax], height[nmax]; vector<int> naive[nmax]; int solved[nmax]; template<class CB> void fill(int a, int f, CB&& cb, vector<int> graph[nmax]) { cb(a); for(auto x : graph[a]) if(x != f) fill(x, a, cb, graph); return; } #define lsb(x) (x & -x) struct AIB { vector<int> v; void init(int n_) { v.assign(n_ + 5, 0); } int query(int a) { int sum = 0; while(a > 0) sum += v[a], a -= lsb(a); return sum; } void update(int p, int x) { while(p < sz(v)) v[p] += x, p += lsb(p); } }; namespace DS { ll sol; AIB occupied; int pin[nmax], pout[nmax], inp; int jump[nmax], p[nmax], d[nmax]; int budget[nmax]; void fill(int a, int f) { //cerr << a << ' ' << f << '\n'; d[a] = d[f] + 1; p[a] = jump[a] = f; if(d[f] + d[jump[jump[f]]] == 2 * d[jump[f]]) jump[a] = jump[jump[f]]; pin[a] = inp++; for(auto x : g[a]) if(x != f) fill(x, a); pout[a] = inp++; return; } void startProcedure(vector<int> nodes, vector<int> cycles) { // nu normalizezi fortat nodurile la minim, dar la fiecare valoare de pe ciclu vezi cum se comporta pana in punctul ala si pui valoarea aia de pe ciclu in ciuda celorlaltor // va fi o mare durere de pula sa scrii normalizarea height[0] = -inf; sol = 0; inp = 1; fill(0, 0); map<int, ll> cyclefree; for(auto x : cycles) solved[x] = 100, d[x] = -1; copy(all(cycles), back_inserter(nodes)); map<pii, int> renrm; for(auto x : nodes) renrm[make_pair(height[x], d[x])]; int cnt = 0; for(auto &[a, b] : renrm) b = cnt++; for(auto x : nodes) height[x] = renrm[make_pair(height[x], d[x])]; for(auto x : nodes) { if(solved[x] == 100) cyclefree[height[x]] += cost[x]; } occupied.init(inp); //cerr << "wow\n"; ll sum = 0, maxpossible = 0; for(auto x : nodes) sum += cost[x]; sort(all(nodes), [&](int a, int b) { return height[a] > height[b]; }); for(auto x : nodes) budget[x] = 0; auto anc = [&](int node) { return occupied.query(pin[node]); }; auto modnode = [&](int node, int p) { occupied.update(pin[node], p), occupied.update(pout[node], -p); }; for(auto x : nodes) { int specialed = 0; if(solved[x] == 100) { specialed = cyclefree[height[x]]; //cerr << x << ' ' << specialed << '\n'; } else { int mine = anc(x), upward = x, mybudget = cost[x]; while(mybudget > 0 && mine > 0) { int tmp = upward; while(upward != 0 && anc(upward) == mine) { if(anc(jump[upward]) == mine) upward = jump[upward]; tmp = upward; upward = p[upward]; } upward = tmp; if(upward != 0) { int u = min(mybudget, budget[upward]); mybudget -= u, budget[upward] -= u; if(budget[upward] == 0) modnode(upward, -1), mine = anc(x); } } sol += mybudget; modnode(x, 1); budget[x] = cost[x]; } maxpossible = max(maxpossible, sol + specialed); } //cerr << maxpossible << '\n'; for(auto x : nodes) solved[x] = 1; sol = sum - maxpossible; return; } } signed main() { cin.tie(0) -> sync_with_stdio(0); int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> father[i] >> height[i] >> cost[i]; naive[i].emplace_back(father[i]); naive[father[i]].emplace_back(i); } ll autoAdd = 0; for(int i = 1; i <= n; i++) { if(solved[i]) continue; vector<int> nodes, cycles; g[n + 1].clear(); g[0].clear(); g[0].emplace_back(n + 1); g[n + 1].emplace_back(0); int x = i; while(solved[x] == 0) { solved[x] = -2; x = father[x]; } while(solved[x] == -2) { solved[x] = -1; x = father[x]; } height[n + 1] = -inf; cost[n + 1] = 0; while(solved[x] == -1) { cycles.emplace_back(x); for(auto a : naive[x]) { if(solved[a] != -1 && solved[a] != 1) { fill(a, x, [&](int node) { nodes.emplace_back(node); if(solved[father[node]] == -1) g[node].emplace_back(n + 1), g[n + 1].emplace_back(node); else g[node].emplace_back(father[node]), g[father[node]].emplace_back(node); solved[node] = 1; }, naive); } } solved[x] = 1; x = father[x]; } DS::startProcedure(nodes, cycles); autoAdd += DS::sol; } cout << autoAdd << '\n'; } /** Istenem! Nu poate fi real. -- Surse verificate */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...