Submission #647248

#	Time	Username	Problem	Language	Result	Execution time	Memory
647248		GusterGoose27	Worst Reporter 4 (JOI21_worst_reporter4)	C++11	100 / 100	343 ms	43920 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.upper_bound(p);
		while (nval != slopes.end() && nval->second <= r) {
			r -= nval->second;
			slopes.erase(nval);
			nval = slopes.upper_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;
}

ll bash(vector<int> &vals, ll c = 0) {
	if (vals.size() == n) {
		for (int i = 0; i < n; i++) {
			if (vals[out_val[i]] > vals[i]) return -1;
		}
		return c;
	}
	ll best = -1;
	int p = vals.size();
	for (int i = 1; i <= 10; i++) {
		vals.push_back(i);
		if (i != MXVAL+1-ratings[p]) c += costs[p];
		ll cval = bash(vals, c);
		if (best == -1 || (cval != -1 && cval < best)) best = cval;
		if (i != MXVAL+1-ratings[p]) c -= costs[p];
		vals.pop_back();
	}
	return best;
}

ll solve() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//ifstream fin("report.in");
	cin >> n;
	ans = 0;
	for (int i = 0; i < n; i++) {
		indeg[i] = 0;
		in_edges[i].clear();
		vis[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		int a;
		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);
	}
	//fin.close();
	return ans;
}

void gen_case() {
	int N = 6;
	ofstream fout("report.in");
	fout << N << "\n";
	for (int i = 0; i < N; i++) {
		fout << (1+(rand() % N)) << " " << (1+(rand() % 10)) << " " << (1+(rand() % 10)) << "\n";
	}
	fout.close();
}

signed main() {
	// srand(time(0));
	// vector<int> v;
	ll ans = solve();
	// ll b = bash(v);
	// cout << ans << " " << b << endl;
	// while (1) {
	// 	gen_case();
	// 	ll ans = solve();
	// 	ll b = bash(v);
	// 	assert(ans == b);
	// }
	cout << ans << "\n";
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'll bash(std::vector<long long int>&, ll)':
worst_reporter2.cpp:104:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  104 |  if (vals.size() == n) {
      |      ~~~~~~~~~~~~^~~~

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