Submission #912488

#	Time	Username	Problem	Language	Result	Execution time	Memory
912488		mickey080929	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	365 ms	145276 KiB

worst_reporter2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll inf = 2e18;

ll nxt[200010];
vector<ll> rev[200010];
ll H[200010], C[200010];
ll vis[200010];
ll st = -1;
ll cy[200010];
vector<ll> v[200010];

void dfs(ll x, ll num) {
	vis[x] = num;
	if (vis[nxt[x]] == num) {
		st = x;
		return;
	}
	if (vis[nxt[x]]) return;
	dfs(nxt[x], num);
}

void push_cycle(ll x, ll num) {
	cy[x] = num;
	v[num].push_back(x);
	if (cy[nxt[x]]) return;
	push_cycle(nxt[x], num);
}

ll par[200010];
multiset<pair<ll,ll>> ms[200010];

ll Find(ll x) {
	if (x == par[x]) return x;
	return par[x] = Find(par[x]);
}

void Union(ll x, ll y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	if (ms[x].size() < ms[y].size()) swap(x, y);
	for (auto &[i, add] : ms[y]) {
		ms[x].insert({i, add});
	}
	par[y] = x;
}

void dfs2(ll x) {
	for (auto &y : rev[x]) {
		dfs2(y);
		Union(x, y);
	}
	ll X = Find(x);
	ll cur = C[x];
	for (auto it = ms[X].upper_bound({H[x], inf}); it != ms[X].end(); ) {
		if (cur < it->second) {
			auto t = *it;
			ms[X].erase(it);
			ms[X].insert({t.first, t.second - cur});
			break;
		}
		cur -= it->second;
		it = ms[X].erase(it);
	}
	ms[X].insert({H[x], C[x]});
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); 
	ll n;
	cin >> n;
	ll ans = 0;
	for (ll i=1; i<=n; i++) {
		cin >> nxt[i] >> H[i] >> C[i];
		H[i] *= -1;
		rev[nxt[i]].push_back(i);
		ans += C[i];
		par[i] = i;
	}
	ll num = 0, num2 = 0;
	for (ll i=1; i<=n; i++) {
		if (vis[i]) continue;
		st = -1;
		dfs(i, ++num);
		if (st != -1) {
			push_cycle(st, ++num2);
		}
	}
	for (ll gr=1; gr<=num2; gr++) {
		map<ll,ll> mp;
		ll pv = -1;
		for (auto &x : v[gr]) {
			for (auto &y : rev[x]) {
				if (cy[y]) continue;
				dfs2(y);
				if (pv == -1) pv = y;
				else Union(pv, y);
			}
			if (mp.find(H[x]) != mp.end()) {
				mp[H[x]] += C[x];
			}
			else {
				mp[H[x]] = C[x];
			}
		}
		ll mx = 0;
		if (pv == -1) {
			for (auto &[i, add] : mp)
				mx = max(mx, add);
		}
		else {
			pv = Find(pv);
			vector<pair<ll,ll>> func;
			for (auto &[i, add] : ms[pv]) {
				func.push_back({i, add});
			}
			for (ll i=0; i+1<func.size(); i++) {
				func[i+1].second += func[i].second;
			}
			for (auto &[i, add] : mp) {
				ll idx = upper_bound(func.begin(), func.end(), make_pair(i, inf)) - func.begin() - 1;
				if (idx == -1) mx = max(mx, add);
				else mx = max(mx, func[idx].second + add);
			}
			mx = max(mx, func.back().second);
		}
		ans -= mx;
	}
	cout << ans << '\n';
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:121:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    for (ll i=0; i+1<func.size(); i++) {
      |                 ~~~^~~~~~~~~~~~

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