Submission #435641

#	Time	Username	Problem	Language	Result	Execution time	Memory
435641		Kevin_Zhang_TW	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	100 / 100	459 ms	71272 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010, inf = 1e9 + 10;

int n;
vector<int> pa, h, c;
vector<int> edge[MAX_N];

// maintain diff
map<int, ll> dp[MAX_N];

void add_pref(int i, int key, ll val) {
	if (val == 0) return;
	dp[i][key] += val;
}
// put dp value into a
void merge(int a, int b) { 
	if (dp[b].size() > dp[a].size()) swap(dp[a], dp[b]);
	// do something
	for (auto [key, val] : dp[b])
		add_pref(a, key, val);
	dp[b].clear();
}
ll qry(map<int,ll>&dp, int x) {
	auto it = dp.lower_bound(x);
	if (it == end(dp)) return 0;
	return it->second;
}

void dfs(int x) {
	for (int u : edge[x])
		dfs(u), merge(x, u);

	dp[x][ h[x] ] += c[x];

	ll v = c[x];
	auto it = dp[x].find(h[x]);

	while (it != begin(dp[x])) {
		ll &d = prev(it)->second;
		if (d <= v) {
			v -= d;
			dp[x].erase(prev(it));
		}
		else {
			d -= v;
			break;
		}
	} 
}
ll cal(vector<int> ring) {
	dp[n].clear();

	for (int x : ring) for (int u : edge[x]) {
		dfs(u);
		merge(n, u);
	}

	ll ret = 0;

	vector<pair<int,ll>> val(AI(dp[n]));
	val.pb(inf, 0);
	for (int i = (int) val.size() - 1;i > 0;--i)
		val[i-1].second += val[i].second; 

	map<int, ll> sum;

	for (int x : ring)
		sum[ h[x] ] += c[x];
	sum[-1] = 0;

	for (auto [k, v] : sum)
		chmax(ret, lower_bound(AI(val), make_pair(k, -1ll))->second + v);

	return ret; 
}

ll min_change_val(int n, vector<int> a, vector<int> h, vector<int> c) {
	::n = n, pa = a, ::h = h, ::c = c;

	ll res = 0;

	vector<int> vis(n), rid(n, -1), on_ring(n);
	
	int cnt_ring = 0;
	for (int i = 0;i < n;++i) if (!vis[i]) {
		vector<int> stk;
		for (int x = i;!vis[x];x = pa[x]) {
			stk.pb(x);
			vis[x] = true;
		}
		DE(i, "stk");
		debug(AI(stk));
		if (rid[ pa[stk.back()] ] == -1) {
			int s = pa[ stk.back() ];
			while (stk.size()) {
				int x = stk.back(); stk.pop_back();
				on_ring[x] = true;
				rid[x] = cnt_ring;
				if (x == s) break;
			}
			++cnt_ring;
		}
		while (stk.size()) {
			int x = stk.back(); stk.pop_back();
			rid[x] = rid[ pa[x] ];
		}
	}
	for (int i = 0;i < n;++i) DE(i, rid[i], on_ring[i]);

	for (int i = 0;i < n;++i) if (!on_ring[i] || !on_ring[ pa[i] ]) {
		DE(i, pa[i]);
		edge[ pa[i] ].pb(i);
	}

	vector<vector<int>> ring(cnt_ring);
	for (int i = 0;i < n;++i) if (on_ring[i])
		ring[ rid[i] ].pb(i);

	for (int i = 0;i < cnt_ring;++i) {
		debug(AI(ring[i]));
		res += cal(ring[i]);
	}

	return accumulate(AI(c), 0ll) - res;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n;
	cin >> n;
	vector<int> a(n), h(n), c(n);
	for (int i = 0;i < n;++i)
		cin >> a[i] >> h[i] >> c[i], --a[i];

	cout << min_change_val(n, a, h, c) << '\n';
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'll min_change_val(int, std::vector<int>, std::vector<int>, std::vector<int>)':
worst_reporter2.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
worst_reporter2.cpp:107:3: note: in expansion of macro 'DE'
  107 |   DE(i, "stk");
      |   ^~
worst_reporter2.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
worst_reporter2.cpp:108:3: note: in expansion of macro 'debug'
  108 |   debug(AI(stk));
      |   ^~~~~
worst_reporter2.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
worst_reporter2.cpp:124:28: note: in expansion of macro 'DE'
  124 |  for (int i = 0;i < n;++i) DE(i, rid[i], on_ring[i]);
      |                            ^~
worst_reporter2.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
worst_reporter2.cpp:127:3: note: in expansion of macro 'DE'
  127 |   DE(i, pa[i]);
      |   ^~
worst_reporter2.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
worst_reporter2.cpp:136:3: note: in expansion of macro 'debug'
  136 |   debug(AI(ring[i]));
      |   ^~~~~

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