oj.uz

Submission #623650

# Submission time Handle Problem Language Result Execution time Memory
623650 2022-08-06T08:31:54 Z valerikk Escape Route (JOI21_escape_route) C++17
35 / 100
 9000 ms 195692 KB 
#include "escape_route.h"
#include <algorithm>
#include <cassert>
#include <limits>

const long long INF = 1e18;

std::vector<long long> calculate_necessary_time(
	int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
	std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
	std::vector<int> V, std::vector<long long> T) {

	std::vector<long long> answer(Q, INF);

	std::vector<std::vector<long long>> dists0(N);
	for (int start = 0; start < N; ++start) {
		std::vector<std::vector<long long>> l(N, std::vector<long long>(N, -1));
		std::vector<std::vector<long long>> c(N, std::vector<long long>(N, -1));
		for (int i = 0; i < M; ++i) {
			l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
			c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];	
		}

		std::vector<long long> dist(N, INF);
		std::vector<bool> used(N, false);
		dist[start] = 0;
		for (int it = 0; it < N; ++it) {
			int u = -1;
			for (int v = 0; v < N; ++v) {
				if (!used[v] && (u == -1 || dist[v] < dist[u])) {
					u = v;
				}
			}
			assert(dist[u] != INF);
			used[u] = true;
			long long rem = dist[u] % S;
			for (int v = 0; v < N; ++v) {
				if (!used[v] && l[u][v] != -1) {
					long long new_dist = dist[u] + l[u][v];
					if (rem + l[u][v] > c[u][v]) {
						new_dist = dist[u] + S - rem + l[u][v];
					}
					dist[v] = std::min(dist[v], new_dist);
				}
			}
		}
		dists0[start] = dist;
	}

	for (int start = 0; start < N; ++start) {
		std::vector<std::vector<long long>> l(N, std::vector<long long>(N, -1));
		std::vector<std::vector<long long>> c(N, std::vector<long long>(N, -1));
		for (int i = 0; i < M; ++i) {
			l[A[i]][B[i]] = l[B[i]][A[i]] = L[i];
			c[A[i]][B[i]] = c[B[i]][A[i]] = C[i];	
		}

		std::vector<long long> stops = {0};
		std::vector<std::vector<long long>> dists;
		while (true) {
			std::vector<long long> dist(N, INF);
			std::vector<bool> used(N, false);
			dist[start] = 0;
			for (int it = 0; it < N; ++it) {
				int u = -1;
				for (int v = 0; v < N; ++v) {
					if (!used[v] && (u == -1 || dist[v] < dist[u])) {
						u = v;
					}
				}
				used[u] = true;
				for (int v = 0; v < N; ++v) {
					if (l[u][v] != -1 && !used[v]) {
						dist[v] = std::min(dist[v], dist[u] + l[u][v]);
					}
				}
			}
			long long stop = INF;
			for (int u = 0; u < N; ++u) {
				for (int v = 0; v < N; ++v) {
					if (l[u][v] != -1) {
						stop = std::min(stop, std::max(stops.back(), c[u][v] - dist[u] - l[u][v] + 1));
					}
				}
			}
			stops.push_back(stop);
			dists.push_back(dist);
			for (int u = 0; u < N; ++u) {
				for (int v = 0; v < N; ++v) {
					if (l[u][v] != -1 && std::max(stops.back(), c[u][v] - dist[u] - l[u][v] + 1) == stop) {
						l[u][v] = -1;
						c[u][v] = -1;
					}
				}
			}
			if (stop == INF) break;
		}

		for (int i = 0; i < Q; ++i) {
			if (U[i] == start) {
				int pos = std::upper_bound(begin(stops), end(stops), T[i]) - begin(stops);
				answer[i] = std::min(answer[i], dists[pos - 1][V[i]]);
				for (int W = 0; W < N; ++W) {
					if (dists[pos - 1][W] != INF) {
						answer[i] = std::min(answer[i], S - T[i] + dists0[W][V[i]]); 
					}
				}
			}
		}
	}

	return answer;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65020 KB Output is correct
2 Correct 61 ms 65044 KB Output is correct
3 Correct 950 ms 65072 KB Output is correct
4 Correct 23 ms 64980 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 26 ms 65048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1532 ms 154260 KB Output is correct
2 Correct 1587 ms 172200 KB Output is correct
3 Correct 1523 ms 153608 KB Output is correct
4 Correct 1728 ms 182008 KB Output is correct
5 Correct 1738 ms 181608 KB Output is correct
6 Correct 25 ms 65016 KB Output is correct
7 Correct 1536 ms 154944 KB Output is correct
8 Correct 513 ms 194060 KB Output is correct
9 Correct 1662 ms 154456 KB Output is correct
10 Correct 1695 ms 181464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65020 KB Output is correct
2 Correct 61 ms 65044 KB Output is correct
3 Correct 950 ms 65072 KB Output is correct
4 Correct 23 ms 64980 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 26 ms 65048 KB Output is correct
7 Correct 1532 ms 154260 KB Output is correct
8 Correct 1587 ms 172200 KB Output is correct
9 Correct 1523 ms 153608 KB Output is correct
10 Correct 1728 ms 182008 KB Output is correct
11 Correct 1738 ms 181608 KB Output is correct
12 Correct 25 ms 65016 KB Output is correct
13 Correct 1536 ms 154944 KB Output is correct
14 Correct 513 ms 194060 KB Output is correct
15 Correct 1662 ms 154456 KB Output is correct
16 Correct 1695 ms 181464 KB Output is correct
17 Correct 1934 ms 156984 KB Output is correct
18 Correct 1797 ms 157024 KB Output is correct
19 Correct 1846 ms 175324 KB Output is correct
20 Correct 1754 ms 156404 KB Output is correct
21 Correct 1944 ms 184396 KB Output is correct
22 Correct 1948 ms 184416 KB Output is correct
23 Correct 1859 ms 157192 KB Output is correct
24 Correct 811 ms 195692 KB Output is correct
25 Correct 1889 ms 156752 KB Output is correct
26 Correct 2007 ms 181672 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65020 KB Output is correct
2 Correct 61 ms 65044 KB Output is correct
3 Correct 950 ms 65072 KB Output is correct
4 Correct 23 ms 64980 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 26 ms 65048 KB Output is correct
7 Correct 1532 ms 154260 KB Output is correct
8 Correct 1587 ms 172200 KB Output is correct
9 Correct 1523 ms 153608 KB Output is correct
10 Correct 1728 ms 182008 KB Output is correct
11 Correct 1738 ms 181608 KB Output is correct
12 Correct 25 ms 65016 KB Output is correct
13 Correct 1536 ms 154944 KB Output is correct
14 Correct 513 ms 194060 KB Output is correct
15 Correct 1662 ms 154456 KB Output is correct
16 Correct 1695 ms 181464 KB Output is correct
17 Correct 1934 ms 156984 KB Output is correct
18 Correct 1797 ms 157024 KB Output is correct
19 Correct 1846 ms 175324 KB Output is correct
20 Correct 1754 ms 156404 KB Output is correct
21 Correct 1944 ms 184396 KB Output is correct
22 Correct 1948 ms 184416 KB Output is correct
23 Correct 1859 ms 157192 KB Output is correct
24 Correct 811 ms 195692 KB Output is correct
25 Correct 1889 ms 156752 KB Output is correct
26 Correct 2007 ms 181672 KB Output is correct
27 Execution timed out 9029 ms 156192 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65020 KB Output is correct
2 Correct 61 ms 65044 KB Output is correct
3 Correct 950 ms 65072 KB Output is correct
4 Correct 23 ms 64980 KB Output is correct
5 Correct 28 ms 64968 KB Output is correct
6 Correct 26 ms 65048 KB Output is correct
7 Correct 1532 ms 154260 KB Output is correct
8 Correct 1587 ms 172200 KB Output is correct
9 Correct 1523 ms 153608 KB Output is correct
10 Correct 1728 ms 182008 KB Output is correct
11 Correct 1738 ms 181608 KB Output is correct
12 Correct 25 ms 65016 KB Output is correct
13 Correct 1536 ms 154944 KB Output is correct
14 Correct 513 ms 194060 KB Output is correct
15 Correct 1662 ms 154456 KB Output is correct
16 Correct 1695 ms 181464 KB Output is correct
17 Correct 1934 ms 156984 KB Output is correct
18 Correct 1797 ms 157024 KB Output is correct
19 Correct 1846 ms 175324 KB Output is correct
20 Correct 1754 ms 156404 KB Output is correct
21 Correct 1944 ms 184396 KB Output is correct
22 Correct 1948 ms 184416 KB Output is correct
23 Correct 1859 ms 157192 KB Output is correct
24 Correct 811 ms 195692 KB Output is correct
25 Correct 1889 ms 156752 KB Output is correct
26 Correct 2007 ms 181672 KB Output is correct
27 Execution timed out 9029 ms 156192 KB Time limit exceeded
28 Halted 0 ms 0 KB -