oj.uz

답안 #647240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647240 2022-10-02T03:13:21 Z GusterGoose27 Worst Reporter 4 (JOI21_worst_reporter4) C++11
0 / 100
 7 ms 5588 KB 
#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;
      |          ^

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 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 -