Submission #647240

#	Time	Username	Problem	Language	Result	Execution time	Memory
647240		GusterGoose27	Worst Reporter 4 (JOI21_worst_reporter4)	C++11	0 / 100	7 ms	5588 KiB

worst_reporter2

#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 (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:107:10: warning: unused variable 'h' [-Wunused-variable]
  107 |   int a, h;
      |          ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21