제출 #1210626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210626		siewjh	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	100 / 100	391 ms	102808 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
typedef long long ll;
bool vis[MAXN], iscyc[MAXN];
int nxt[MAXN];
ll rate[MAXN], cost[MAXN], mxv[MAXN];
vector<int> adj[MAXN], cycle;
map<ll, ll> rd[MAXN];
int dfs(int x){
	vis[x] = 1;
	int nn = nxt[x], cst;
	if (vis[nn]) cst = nn;
	else cst = dfs(nn);
	if (cst != -1){
		cycle.push_back(x); iscyc[x] = 1;
	}
	if (x == cst) cst = -1;
	return cst;
}
void dfs2(int x){
	vis[x] = 1;
	mxv[x] = cost[x];
	for (int nn : adj[x]){
		dfs2(nn);
		mxv[x] += mxv[nn];
		if (rd[nn].size() > rd[x].size()) swap(rd[nn], rd[x]);
		for (auto [p, c] : rd[nn]) rd[x][p] += c;
	}
	auto it = rd[x].lower_bound(rate[x]);
	ll rem = cost[x];
	while (it != rd[x].begin()){
		it--;
		if (it->second > rem){
			it->second -= rem; break;
		}
		else{
			rem -= it->second;
			it = rd[x].erase(it);
		}
	}
	rd[x][rate[x]] += cost[x];
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nums; cin >> nums;
	for (int i = 1; i <= nums; i++){
		cin >> nxt[i] >> rate[i] >> cost[i];
		adj[nxt[i]].push_back(i);
	}
	ll ans = 0;
	for (int i = 1; i <= nums; i++){
		if (vis[i]) continue;
		cycle.clear();
		dfs(i);
		map<ll, ll> m;
		ll smxv = 0, res;
		for (int cn : cycle){
			smxv += cost[cn];
			m[rate[cn]] += cost[cn]; m[rate[cn] - 1] -= cost[cn];
			for (int nn : adj[cn]){
				if (iscyc[nn]) continue;
				dfs2(nn);
				smxv += mxv[nn];
				if (rd[nn].size() > m.size()) swap(rd[nn], m);
				for (auto [p, c] : rd[nn]) m[p] += c;
			}
		}
		res = smxv;
		auto it = m.end();
		while (it != m.begin()){
			it--;
			smxv -= it->second;
			res = min(res, smxv);
		}
		ans += res;
	}
	cout << ans;
}

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