Submission #1208655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208655		k1r1t0	Road Closures (APIO21_roads)	C++20	100 / 100	169 ms	60360 KiB

roads

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 110000;

struct fenwick {
	vector<ll> ff;
	vector<int> cc;
	int n;
	fenwick() {}
	fenwick(int n) {
		this->n = n;
		ff = vector<ll>(n + 1, 0);
		cc = vector<int>(n + 1, 0);
	}
	void upd(int k, ll x) {
		for (; k <= n; k += k & -k) {
			ff[k] += x;
			cc[k]++;
		}
	}
	ll _get(int k) {
		ll ans = 0;
		for (; k >= 1; k -= k & -k)
			ans += ff[k];
		return ans;
	}
	ll get(int k) {
		int cnt = 0, pos = 0;
		for (int u = (1 << 20); u > 0; u /= 2)
			if (pos + u <= n && cnt + cc[pos + u] <= k) {
				pos += u;
				cnt += cc[pos];
			}
		return _get(pos);
	}
};

int n, k, sh[N];
ll dp[N][2];
set<array<int, 2>> vert, g[N];
fenwick ff[N];
vector<array<int, 2>> h[N];
bool bad[N], used[N];

void rem(int v, int u, int w) {
	int pos = lower_bound(begin(h[v]), end(h[v]), array<int, 2>{-w, u}) - begin(h[v]) + 1;
	sh[v]++;
	ff[v].upd(pos, w);
}

ll sum(int v, int t) {
	t = min(t, sh[v]);
	return ff[v].get(t);
}

ll dfs(int v, int p = -1) {
	used[v] = true;
	ll base = 0;
	vector<ll> add;
	for (auto [u, w] : g[v]) if (u != p) {
		dfs(u, v);
		dp[u][1] = max(dp[u][0], dp[u][1] + w);
		base += dp[u][0];
		add.push_back(dp[u][1] - dp[u][0]);
	}
	sort(begin(add), end(add), greater<ll>());
	for (int f = 0; f < 2; f++) {
		dp[v][f] = 0;
		ll addsum = 0;
		for (int a = 0; a <= min((int) add.size(), k - f); a++) {
			int b = k - f - a;
			dp[v][f] = max(dp[v][f], base + addsum + sum(v, b));
			if (a < (int) add.size())
				addsum += add[a];
		}
	}
	return max(dp[v][0], dp[v][1]);
}

vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		U[i]++; V[i]++;
		g[U[i]].insert({V[i], W[i]});
		g[V[i]].insert({U[i], W[i]});
	}
	for (int i = 1; i <= n; i++) {
		vector<array<int, 2>> ch;
		for (auto [u, w] : g[i])
			h[i].push_back({-w, u});
		sort(begin(h[i]), end(h[i]));
		ff[i] = fenwick((int) g[i].size());
		vert.insert({(int) g[i].size(), i});
	}
	ll base = 0;
	vector<ll> ans;
	for (k = 0; k <= n - 1; k++) {
		while (!vert.empty() && (*vert.begin())[0] <= k) {
			int v = (*vert.begin())[1];
			vert.erase(vert.begin());
			bad[v] = true;
			for (auto [u, w] : g[v]) {
				g[u].erase({v, w});
				rem(u, v, w);
			}
			base += sum(v, sh[v]);
		}
		if (k == 0) ans.push_back(0);
		else {
			ll cur = base;
			for (auto [s, v] : vert)
				used[v] = false;
			for (auto [s, v] : vert)
				if (!used[v]) cur += dfs(v);
			ans.push_back(cur);
		}
	}
	ll sum = accumulate(begin(W), end(W), 0ll);
	for (ll &x : ans)
		x = sum - x;
	return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22