Submission #1047012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047012		pavement	Closing Time (IOI23_closing)	C++17	9 / 100	1133 ms	1299124 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;

#define pb push_back
#define eb emplace_back

int to[200005];
ll distX[200005], distY[200005], distX_copy[200005], distY_copy[200005];
vector<ii> adj[200005];
vector<ll> vec_0[200005], vec_1[200005], vec_2[200005];

void get_dist(int u, ll dist[], int e = -1) {
	for (auto [v, w] : adj[u]) if (v != e) {
		dist[v] = dist[u] + w;
		get_dist(v, dist, u);
	}
}

bool init(int u, int Y, int e = -1) {
	if (u == Y) {
		return 1;
	}
	for (auto [v, _] : adj[u]) if (v != e) {
		if (init(v, Y, u)) {
			to[u] = v;
			return 1;
		}
	}
	return 0;
}

void dp(int u, int e = -1) {
	vec_0[u].pb(distX[u]);
	vec_1[u].pb((ll)2e18);
	vec_1[u].pb(max(distX[u], distY[u]));
	vec_2[u].pb(distY[u]);
	if (to[u] != -1) {
		for (auto [v, _] : adj[u]) if (v != e) {
			dp(v, u);
			vector<ll> new_vec_0(vec_0[u].size() + vec_1[v].size() - 1, (ll)2e18);
			for (int i = 0; i < (int)vec_0[u].size(); i++) {
				for (int j = 0; j < (int)vec_1[v].size(); j++) {
					ll oth = (v == to[u] ? min(j < (int)vec_0[v].size() ? vec_0[v][j] : (ll)2e18, vec_1[v][j]) : (j < (int)vec_0[v].size() ? vec_0[v][j] : (ll)2e18));
					new_vec_0[i + j] = min(new_vec_0[i + j], vec_0[u][i] + oth);
				}
			}
			swap(vec_0[u], new_vec_0);
			vector<ll> new_vec_1(vec_1[u].size() + vec_1[v].size() - 1, (ll)2e18);
			for (int i = 0; i < (int)vec_1[u].size(); i++) {
				for (int j = 0; j < (int)vec_1[v].size(); j++) {
					ll oth = (v == to[u] && j < (int)vec_2[v].size() ? min(vec_1[v][j], vec_2[v][j]) : vec_1[v][j]);
					new_vec_1[i + j] = min(new_vec_1[i + j], vec_1[u][i] + oth);
				}
			}
			swap(vec_1[u], new_vec_1);
			vector<ll> new_vec_2(vec_2[u].size() + vec_2[v].size() - 1, (ll)2e18);
			for (int i = 0; i < (int)vec_2[u].size(); i++) {
				for (int j = 0; j < (int)vec_2[v].size(); j++) {
					new_vec_2[i + j] = min(new_vec_2[i + j], vec_2[u][i] + vec_2[v][j]);
				}
			}
			swap(vec_2[u], new_vec_2);
		}
	} else {
		for (auto [v, _] : adj[u]) if (v != e) {
			dp(v, u);
			vector<ll> new_vec_0(vec_0[u].size() + vec_0[v].size() - 1, (ll)2e18);
			for (int i = 0; i < (int)vec_0[u].size(); i++) {
				for (int j = 0; j < (int)vec_0[v].size(); j++) {
					new_vec_0[i + j] = min(new_vec_0[i + j], vec_0[u][i] + vec_0[v][j]);
				}
			}
			swap(vec_0[u], new_vec_0);
			vector<ll> new_vec_1(vec_1[u].size() + vec_1[v].size() - 1, (ll)2e18);
			for (int i = 0; i < (int)vec_1[u].size(); i++) {
				for (int j = 0; j < (int)vec_1[v].size(); j++) {
					ll oth;
					if (j < (int)vec_0[v].size()) {
						oth = min({vec_1[v][j], vec_0[v][j], vec_2[v][j]});
					} else {
						oth = vec_1[v][j];
					}
					new_vec_1[i + j] = min(new_vec_1[i + j], vec_1[u][i] + oth);
				}
			}
			swap(vec_1[u], new_vec_1);
			vector<ll> new_vec_2(vec_2[u].size() + vec_2[v].size() - 1, (ll)2e18);
			for (int i = 0; i < (int)vec_2[u].size(); i++) {
				for (int j = 0; j < (int)vec_2[v].size(); j++) {
					new_vec_2[i + j] = min(new_vec_2[i + j], vec_2[u][i] + vec_2[v][j]);
				}
			}
			swap(vec_2[u], new_vec_2);
		}
	}
	vec_0[u].insert(vec_0[u].begin(), 0);
	vec_1[u].insert(vec_1[u].begin(), 0);
	vec_2[u].insert(vec_2[u].begin(), 0);
	//~ cout << "@ " << u << ":\n";
	//~ for (auto i : vec_0[u]) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	//~ for (auto i : vec_1[u]) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
	//~ for (auto i : vec_2[u]) {
		//~ cout << i << ' ';
	//~ }
	//~ cout << '\n';
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
	int ans = -1;
	for (int i = 0; i < N - 1; i++) {
		adj[U[i]].eb(V[i], W[i]);
		adj[V[i]].eb(U[i], W[i]);
	}
	get_dist(X, distX);
	get_dist(Y, distY);
	copy(distX, distX + N, distX_copy);
	copy(distY, distY + N, distY_copy);
	sort(distX_copy, distX_copy + N);
	sort(distY_copy, distY_copy + N);
	for (int i = 1; i < N; i++) {
		distY_copy[i] += distY_copy[i - 1];
	}
	ll rs = 0;
	for (int i = 0; i < N; i++) {
		rs += distX_copy[i];
		if (rs > K) {
			break;
		}
		auto it = upper_bound(distY_copy, distY_copy + N, K - rs);
		ans = max(ans, i + 1 + (int)(it - distY_copy));
	}
	fill(to, to + N, -1);
	init(X, Y);
	dp(X);
	assert((int)vec_1[X].size() == 2 * N + 1);
	for (int i = 0; i <= 2 * N; i++) {
		if ((i < (int)vec_0[X].size() && vec_0[X][i] <= K) || vec_1[X][i] <= K) {
			ans = max(ans, i);
		}
	}
	assert(ans != -1);
	for (int i = 0; i < N; i++) {
		adj[i].clear();
		vec_0[i].clear();
		vec_1[i].clear();
		vec_2[i].clear();
		distX[i] = distY[i] = to[i] = 0;
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 9 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17