Submission #532822

#TimeUsernameProblemLanguageResultExecution timeMemory
532822fhvirusWorst Reporter 4 (JOI21_worst_reporter4)C++17
79 / 100
414 ms94628 KiB
// Knapsack DP is harder than FFT. #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define ff first #define ss second #define pb emplace_back #define AI(x) begin(x),end(x) #ifdef OWO #define debug(args...) SDF(#args, args) #define OIU(args...) ostream& operator<<(ostream&O,args) #define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;} LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss) template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));} template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';} #else #define debug(...) ((void)0) #endif const int kN = 200002; int N, A[kN], H[kN], C[kN]; map<int, ll> dp[kN]; void add(map<int, ll>& mp, int pos, ll val) { mp[pos] += val; while (val > 0) { auto it = mp.lower_bound(pos); if (it == begin(mp)) break; it = prev(it); ll d = min(val, it->ss); val -= d; it->ss -= d; if (it->ss == 0) mp.erase(it); } } void merge(map<int, ll>& a, map<int, ll>& b) { if (a.size() < b.size()) swap(a, b); for (const auto& [pos, val]: b) a[pos] += val; } int indeg[kN]; vector<vector<int>> cycles; int vis[kN], tot; void dfs(int u) { vis[u] = tot; int v = A[u]; if (vis[v] == 0) dfs(v); else if (vis[v] == tot) { vector<int> cycle; do { cycle.emplace_back(v); v = A[v]; } while (v != u); cycles.push_back(cycle); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i <= N; ++i) { cin >> A[i] >> H[i] >> C[i]; ++indeg[A[i]]; } for (int i = 1; i <= N; ++i) if (vis[i] == 0) { ++tot; dfs(i); } queue<int> q; for (int i = 1; i <= N; ++i) if (indeg[i] == 0) q.push(i); while (!q.empty()) { int i = q.front(); q.pop(); add(dp[i], H[i], C[i]); merge(dp[A[i]], dp[i]); if ((--indeg[A[i]]) == 0) q.push(A[i]); } ll ans = accumulate(C + 1, C + N + 1, 0ll); for (const vector<int>& cycle: cycles) { map<int, ll> mp; for (const int& u: cycle) { merge(mp, dp[u]); add(mp, H[u], C[u]); } for (const auto& [pos, val]: mp) ans -= val; } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...