Submission #532838

#	Time	Username	Problem	Language	Result	Execution time	Memory
532838		8e7	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	384 ms	58220 KiB

worst_reporter2

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
typedef map<int, ll> mp;
int to[maxn], deg[maxn];
bool cy[maxn], vis[maxn];
ll h[maxn], c[maxn];
vector<int> adj[maxn];

void comb(mp &a, mp &b) {
	if (a.size() < b.size()) swap(a, b);
	for (auto i:b) a[i.ff] += i.ss;
}
mp dfs(int n, int par) {
	mp ret;
	for (int v:adj[n]) {
		if (v != par && !cy[v]) {
			mp tmp = dfs(v, n);
			comb(ret, tmp);
		}
	}
	ret[1] += c[n];
	ret[h[n]] -= c[n];
	ret[h[n] + 1] += c[n];
	if (ret[h[n]] < 0 && !cy[n]) {
		//debug("rem", n, ret[h[n] + 1]);
		ll val = ret[h[n]];
		auto it = ret.lower_bound(h[n]);

		vector<int> rem;
		ret[h[n]] = 0;
		rem.push_back(h[n]);
		while (it != ret.begin() && val < 0) {
			it = prev(it);
			if (it->ss + val > 0) {
				it->ss += val;
				break;
			} else {
				val += it->ss;
				it->ss = 0;
				rem.push_back(it->ff);
			}
		}
		for (int i:rem) ret.erase(ret.find(i));
	}
	debug(n);
	for (auto i:ret) debug(i.ff, i.ss);
	return ret;
}
int main() {
	io
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) cy[i] = 1;
	for (int i = 1;i <= n;i++) {
		cin >> to[i] >> h[i] >> c[i];	
		deg[to[i]]++;
		adj[to[i]].push_back(i);
	}
	queue<int> que;
	for (int i = 1;i <= n;i++) {
		if (deg[i] == 0) que.push(i);
	}
	while (que.size()) {
		int cur = que.front();que.pop();
		cy[cur] = 0;
		if (--deg[to[cur]] == 0) que.push(to[cur]);
	}
	ll ans = 0;
	for (int i = 1;i <= n;i++) {
		if (cy[i] && !vis[i]) {
			//debug(i);
			int cur = i;
			mp v;
			ll best = inf, val = 0;
			do {
				vis[cur] = 1;
				mp tmp = dfs(cur, 0);
				comb(v, tmp);

				cur = to[cur];
			} while (!vis[cur]);

			if (!v[1]) best = 0;
			for (auto j:v) {
				val += j.ss;
				//debug(j.ff, val);
				best = min(best, val);
			}
			ans += best;	
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'mp dfs(int, int)':
worst_reporter2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
worst_reporter2.cpp:64:2: note: in expansion of macro 'debug'
   64 |  debug(n);
      |  ^~~~~
worst_reporter2.cpp:12:20: warning: statement has no effect [-Wunused-value]
   12 | #define debug(...) 0
      |                    ^
worst_reporter2.cpp:65:19: note: in expansion of macro 'debug'
   65 |  for (auto i:ret) debug(i.ff, i.ss);
      |                   ^~~~~
worst_reporter2.cpp:65:12: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   65 |  for (auto i:ret) debug(i.ff, i.ss);
      |            ^

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