Submission #907458

#TimeUsernameProblemLanguageResultExecution timeMemory
907458tvladm2009Worst Reporter 4 (JOI21_worst_reporter4)C++17
0 / 100
6 ms19040 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define int long long #define ll long long #define all(a) (a).begin(), (a).end() #define pii pair<int, int> const int N = 2e5 + 7; int a[N], h[N], c[N]; vector<int> g[N]; map<int, int> mp[N]; void dfs(int u) { for (auto v : g[u]) { dfs(v); if (mp[v].size() > mp[u].size()) swap(mp[u], mp[v]); for (auto it : mp[v]) mp[u][it.first] += it.second; } auto it = mp[u].find(h[u]); if (it == mp[u].end()) { mp[u][h[u]] = c[u]; it = mp[u].find(a[u]); } else { mp[u][h[u]] += c[u]; } ll func = c[u]; while (it != mp[u].begin() && prev(it)->second < func) { func -= prev(it)->second; mp[u].erase(prev(it)); } if (it != mp[u].begin()) prev(it)->second -= func; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i] >> h[i] >> c[i]; for (int i = 1; i <= n; i++) if (a[i] != i) g[a[i]].push_back(i); dfs(1); ll sum = 0; for (int i = 1; i <= n; i++) sum += c[i]; for (auto it : mp[1]) sum -= it.second; cout << sum << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...