#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int MAXN = 2e5;
const int MXVAL = 1e9;
int n;
int ratings[MAXN];
int indeg[MAXN];
vector<int> in_edges[MAXN];
int out_val[MAXN];
int costs[MAXN];
bool vis[MAXN];
ll ans = 0;
class slopeset {
public:
map<int, ll> slopes; // positive values
ll init_val = 0;
slopeset(ll ival = 0) {
init_val = ival;
}
void merge(slopeset *other) {
init_val += other->init_val;
for (auto it: other->slopes) {
slopes[it.first] += it.second;
}
delete other;
}
void insert(int p, ll c_diff) { // it is c_diff cheaper at point p
ll r = c_diff;
auto nval = slopes.lower_bound(p);
while (nval != slopes.end() && nval->second <= r) {
r -= nval->second;
slopes.erase(nval);
nval = slopes.lower_bound(p);
}
if (nval != slopes.end()) slopes[nval->first] -= r;
slopes[p] = c_diff;
}
int size() {
return slopes.size();
}
};
slopeset *ssets[MAXN];
void prune(int cur) {
vis[cur] = 1;
ssets[cur] = new slopeset(costs[cur]);
for (int nxt: in_edges[cur]) {
if (ssets[nxt]->size() > ssets[cur]->size()) {
ssets[nxt]->merge(ssets[cur]);
ssets[cur] = ssets[nxt];
}
else ssets[cur]->merge(ssets[nxt]);
}
ssets[cur]->insert(ratings[cur], costs[cur]);
int nxt = out_val[cur];
indeg[nxt]--;
if (!indeg[nxt]) prune(nxt);
}
slopeset *sset;
void collect_vals(int cur, map<int, ll> &saved) {
vis[cur] = 1;
for (int nxt: in_edges[cur]) {
if (indeg[nxt]) continue;
if (ssets[nxt]->size() > sset->size()) {
ssets[nxt]->merge(sset);
sset = ssets[nxt];
}
else sset->merge(ssets[nxt]);
}
sset->init_val += costs[cur];
saved[ratings[cur]] += costs[cur];
if (!vis[out_val[cur]]) collect_vals(out_val[cur], saved);
}
void add_to(int cur) {
map<int, ll> saved; // amount saved by choosing this value
sset = new slopeset();
collect_vals(cur, saved);
if (saved.find(MXVAL) == saved.end()) saved[MXVAL] = 0;
ll cur_costs = sset->init_val;
auto spos = sset->slopes.begin();
ll best = -1;
for (auto it: saved) {
while (spos != sset->slopes.end() && spos->first <= it.first) {
cur_costs -= spos->second;
spos++;
}
if (best == -1 || cur_costs-it.second < best) best = cur_costs-it.second;
}
ans += best;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) {
int a, h;
cin >> a >> ratings[i] >> costs[i];
a--;
ratings[i] = MXVAL+1-ratings[i];
indeg[a]++;
in_edges[a].push_back(i);
out_val[i] = a;
}
for (int i = 0; i < n; i++) {
if (!vis[i] && indeg[i] == 0) prune(i);
}
for (int i = 0; i < n; i++) {
if (!vis[i]) add_to(i);
}
cout << ans << "\n";
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:107:10: warning: unused variable 'h' [-Wunused-variable]
107 | int a, h;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5588 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
5548 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5588 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
5548 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5588 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
5548 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
