Submission #932618

#TimeUsernameProblemLanguageResultExecution timeMemory
932618ksujay2Worst Reporter 4 (JOI21_worst_reporter4)C++17
79 / 100
865 ms169140 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MXN = 2e5 + 1; const int MX = 1e9; struct node { ll v; node *left, *right; node() { v = 0, left = right = 0; } void print(int lb, int rb) { if(lb == rb) cout << lb << ":" << v << " "; else { int m = (lb + rb) / 2; if(left) left->print(lb, m); if(right) right->print(m + 1, rb); } } ll del(ll rem, int r, int lb, int rb) { r = min(r, rb); if(r < lb) return 0; if(rb == r && v <= rem) { ll d = v; v -= d; left = right = 0; return d; } if(rb == r && lb == rb) { v -= rem; return rem; } int m = (lb + rb) / 2; ll d = right ? right->del(rem, r, m + 1, rb) : 0; if(rem - d > 0) { d += left ? left->del(rem - d, r, lb, m) : 0; } v -= d; return d; } }; void upd(node* cur, int k, ll v) { int lb = 1, rb = MX; while(lb != rb) { cur->v += v; int m = (lb + rb) / 2; if(k <= m) { if(!cur->left) cur->left = new node(); cur = cur->left; rb = m; } else { if(!cur->right) cur->right = new node(); cur = cur->right; lb = m + 1; } } cur->v += v; } void merge(node* cur, node* other) { other->v += cur->v; if(cur->left) { if(other->left) { merge(cur->left, other->left); } else { other->left = cur->left; } } if(cur->right) { if(other->right) { merge(cur->right, other->right); } else { other->right = cur->right; } } delete(cur); } int A[MXN], H[MXN], C[MXN], in[MXN]; node *segts[MXN]; int main() { int N; cin >> N; ll sm = 0; for(int i = 1; i <= N; i++) { cin >> A[i] >> H[i] >> C[i]; in[A[i]]++; segts[i] = new node(); sm += C[i]; } queue<int> q; for(int i = 1; i <= N; i++) if(in[i] == 0) q.push(i); while(!q.empty()) { int s = q.front(); q.pop(); // cout << s << endl; // segts[s]->print(1, MX); // cout << endl; segts[s]->del(C[s], H[s] - 1, 1, MX); upd(segts[s], H[s], C[s]); merge(segts[s], segts[A[s]]); if(--in[A[s]] == 0) q.push(A[s]); } for(int i = 1; i <= N; i++) { if(in[i] != 0) { // cout << i << endl; vector<int> cyc; cyc.push_back(i); while(in[A[cyc.back()]]) { in[A[cyc.back()]] = 0; cyc.push_back(A[cyc.back()]); } cyc.pop_back(); for(int u : cyc) { if(u != i) { merge(segts[u], segts[i]); } } for(int u : cyc) { segts[i]->del(C[u], H[u] - 1, 1, MX); upd(segts[i], H[u], C[u]); } // segts[i]->print(1, MX); // cout << endl; sm -= segts[i]->v; } } cout << sm << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...