Submission #531834

#	Time	Username	Problem	Language	Result	Execution time	Memory
531834		sidon	Road Closures (APIO21_roads)	C++17	66 / 100	248 ms	49376 KiB

roads

#include <bits/stdc++.h>
using namespace std;
 
template<class T>
using ii = array<T, 2>;
using ll = long long;
using vi = vector<int>;
 
const int Z = 1e5;
const ll INF = 5e13;
 
struct BIT {
	vi a;
	vector<ii<int>> vals;
	vector<ll> b;
	int n, sz {};
	void addVal(ii<int> v) {
		vals.push_back(v);
	}
	void init() {
		sort(begin(vals), end(vals));
		n = size(vals) + 1;
		b.resize(n);
		a.resize(n);
	}
	void insert(ii<int> v) {
		int i = 1 + lower_bound(begin(vals), end(vals), v) - begin(vals);
		for(++sz; i<n; i+=i&-i) {
			a[i] += 1;
			b[i] += v[0];
		}
	}
	ll query(int v) {
		if(v > sz) return INF;
		int i = 0; ll s = 0;
		for(int j = 1<<17; j /= 2; ) if(i+j < n && a[i+j] <= v) {
			i += j;
			v -= a[i];
			s += b[i];
		}
		return s;
	}
} s[Z];
 
int deg[Z], k;
bool vis[Z];
vector<ii<int>> g[Z];
 
ii<ll> dfs(int u) {
	ii<ll> res {INF, INF};
	vis[u] = 1;
	
	vector<ii<ll>> x;
	for(const auto [v, w] : g[u]) if(!vis[v]) {
		x.push_back(dfs(v));
		x.back()[1] += w;
	}
 
	ll cost {};
 
	for(auto &[i, j] : x) {
		cost += i;
		i -= j;
	}
	sort(rbegin(x), rend(x));
 
	for(int i = 0; ; ++i) {
		for(int j : {0, 1})
			res[j] = min(res[j], cost + s[u].query(max(0, (deg[u] - k) - i - j)));
 
		if(i == int(size(x))) break;
		cost -= x[i][0];
	}
 
	return res;
}
 
vector<ll> minimum_closure_costs(int N, vi U, vi V, vi W) {
	
	for(int i = 0; i + 1 < N; ++i) {
		g[U[i]].push_back({V[i], W[i]});
		g[V[i]].push_back({U[i], W[i]});
		++deg[U[i]], ++deg[V[i]];
	}
 
	vector<ii<int>> a;
	vector<ll> res(N);
 
	for(int u = 0; u < N; ++u) {
		sort(begin(g[u]), end(g[u]), [&](const auto &i, const auto &j) {
			return deg[i[0]] > deg[j[0]];
		});
		a.push_back({int(size(g[u])), u});
		for(const auto &[v, w] : g[u])
			s[u].addVal({w, v});
		s[u].init();
	}
	sort(rbegin(a), rend(a));
 
	for(k = 0; k < N; ++k) {
		while(!empty(a) && a.back()[0] < k)
			a.pop_back();
 
		for(const auto &[_d, u] : a) {
			while(!empty(g[u]) && deg[g[u].back()[0]] < k) {
				s[u].insert({g[u].back()[1], g[u].back()[0]});
			 	g[u].pop_back();
			}
			vis[u] = 0;
		}
 
		for(const auto &[_d, u] : a)
			if(!vis[u]) res[k] += dfs(u)[0];
	}
 
	return res;
}

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