oj.uz

Submission #1046976

# Submission time Handle Problem Language Result Execution time Memory
1046976 2024-08-07T07:14:27 Z pavement Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 1255824 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];
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_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++) {
					ll oth = (v == to[u] ? min(vec_0[v][j], vec_1[v][j]) : vec_0[v][j]);
					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);
}

int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
	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);
	fill(to, to + N, -1);
	init(X, Y);
	dp(X);
	int ans = -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 = 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 1091 ms 1255824 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 4 ms 21084 KB Output is correct
3 Correct 2 ms 21084 KB Output is correct
4 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
5 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 4 ms 21084 KB Output is correct
3 Correct 2 ms 21084 KB Output is correct
4 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
5 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 4 ms 21084 KB Output is correct
3 Correct 2 ms 21084 KB Output is correct
4 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
5 Halted 0 ms 0 KB -

Subtask #5
0.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 4 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
6 Halted 0 ms 0 KB -

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 4 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
6 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 4 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
6 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 4 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
6 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 4 ms 21084 KB Output is correct
4 Correct 2 ms 21084 KB Output is correct
5 Incorrect 3 ms 21084 KB 1st lines differ - on the 1st token, expected: '34', found: '27'
6 Halted 0 ms 0 KB -