Submission #564542

#	Time	Username	Problem	Language	Result	Execution time	Memory
564542		hollwo_pelw	Road Closures (APIO21_roads)	C++17	5 / 100	129 ms	26644 KiB

roads

#include "roads.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e5 + 5;
 
multiset<long long> st[MAXN];
long long sum[MAXN], dp[MAXN][2];
int deg[MAXN], vis[MAXN];
vector<pair<int, int>> adj[MAXN];
 
inline void upd(int u, long long v, int op) {
	sum[u] += op * v;
	if (op == +1) 
		st[u].insert(v);
	if (op == -1) 
		st[u].erase(st[u].find(v));
}
 
void solve(int u) {
	vector<long long> add, del;
	long long tot = 0;
 
	// need to del
	int X = vis[u], lim = deg[u] - X;
 
	while ((int)st[u].size() > lim)
		upd(u, *st[u].rbegin(), -1);
 
	for (auto [v, w] : adj[u]) {
		if (deg[v] <= X) break;
		if (vis[v] == X) continue;
		vis[v] = X;
 
		solve(v);
		tot += dp[v][0];
 
		add.push_back(dp[v][1] + w - dp[v][0]), upd(u, dp[v][1] + w - dp[v][0], +1);
	}
 
	for (int i = 0; i < 2; i++) {
		while ((int)st[u].size() > lim - i)
			del.push_back(*st[u].rbegin()), upd(u, *st[u].rbegin(), -1);
		dp[u][i] = tot + sum[u];
	}
}
 
vector<long long> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
	for (int i = 0; i < N - 1; i++) {
		deg[U[i]] ++, deg[V[i]] ++;
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}
	for (int i = 0; i < N; i++)
		sort(adj[i].begin(), adj[i].end(), [&](const pair<int, int> &x, const pair<int, int> &y){ return deg[x.first] > deg[y.first]; });
 
	vector<long long> res(N);
 
	res[0] = accumulate(W.begin(), W.end(), 0ll);
 
	vector<int> p(N);
	iota(p.begin(), p.end(), 0);
	sort(p.begin(), p.end(), [&](const int &i, const int &j){
		return deg[i] < deg[j];
	});
 
	for (int X = 1, i = 0; X < N; X++) {
		for (; i < N && deg[p[i]] == X; i++) {
			for (auto [v, w] : adj[p[i]]) {
				if (deg[v] <= X) break;
				upd(v, w, 1);
			}
		}
 
		long long ans = 0;
 
		for (int j = i; j < N; j++)
			if (vis[p[j]] != X) {
				vis[p[j]] = X;
				solve(p[j]);
				ans += dp[p[j]][0];
			}
 
		res[X] = ans;
	}
 
	return res;
}

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