oj.uz

Submission #1047012

# Submission time Handle Problem Language Result Execution time Memory
1047012 2024-08-07T07:38:00 Z pavement Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 1299124 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1133 ms 1299124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 2 ms 21084 KB Output is correct
4 Correct 3 ms 21080 KB Output is correct
5 Correct 3 ms 21136 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 4 ms 21132 KB Output is correct
9 Correct 3 ms 21084 KB Output is correct
10 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 2 ms 21084 KB Output is correct
4 Correct 3 ms 21080 KB Output is correct
5 Correct 3 ms 21136 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 4 ms 21132 KB Output is correct
9 Correct 3 ms 21084 KB Output is correct
10 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21084 KB Output is correct
3 Correct 2 ms 21084 KB Output is correct
4 Correct 3 ms 21080 KB Output is correct
5 Correct 3 ms 21136 KB Output is correct
6 Correct 3 ms 21084 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 4 ms 21132 KB Output is correct
9 Correct 3 ms 21084 KB Output is correct
10 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
11 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21136 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 2 ms 21084 KB Output is correct
9 Correct 2 ms 21084 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Correct 2 ms 21084 KB Output is correct
12 Correct 3 ms 21084 KB Output is correct
13 Correct 3 ms 21084 KB Output is correct
14 Correct 4 ms 20996 KB Output is correct
15 Correct 3 ms 21080 KB Output is correct
16 Correct 3 ms 21084 KB Output is correct
17 Correct 2 ms 21084 KB Output is correct
18 Correct 3 ms 21084 KB Output is correct
19 Correct 3 ms 21080 KB Output is correct
20 Correct 3 ms 21084 KB Output is correct
21 Correct 3 ms 21084 KB Output is correct
22 Correct 3 ms 21084 KB Output is correct
23 Correct 3 ms 21204 KB Output is correct
24 Correct 3 ms 21084 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21136 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 4 ms 21132 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
12 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21136 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 4 ms 21132 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
12 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21136 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 4 ms 21132 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
12 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21084 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Correct 3 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Correct 3 ms 21080 KB Output is correct
6 Correct 3 ms 21136 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 21084 KB Output is correct
9 Correct 4 ms 21132 KB Output is correct
10 Correct 3 ms 21084 KB Output is correct
11 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '44', found: '52'
12 Halted 0 ms 0 KB -