oj.uz

Submission #623662

# Submission time Handle Problem Language Result Execution time Memory
623662 2022-08-06T08:59:47 Z valerikk Escape Route (JOI21_escape_route) C++17
70 / 100
 8952 ms 187784 KB 
#include "escape_route.h"
#include <algorithm>
#include <cassert>
#include <limits>

static const long long INF = 1e18;
static const int MAX_N = 61;
static const int MAX_M = 1771;

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};
		static long long dists[2 * MAX_M][MAX_N];
		while (true) {
			static long long dist[MAX_N];
			static bool used[MAX_N];
			std::fill(dist, dist + N, INF);
			std::fill(used, 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;
					}
				}
				if (dist[u] == INF) break;
				used[u] = true;
				for (int v = 0; v < N; ++v) {
					if (!used[v] && l[u][v] != -1) {
						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) {
						long long cur = c[u][v] - dist[u] - l[u][v] + 1;
						stop = std::min(stop, std::max(stops.back(), cur));
					}
				}
			}
			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;
					}
				}
			}
			if (stop > stops.back()) {
				std::copy(dist, dist + N, dists[(int) stops.size() - 1]);
				stops.push_back(stop);
			}
			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 64924 KB Output is correct
2 Correct 60 ms 64996 KB Output is correct
3 Correct 864 ms 64980 KB Output is correct
4 Correct 24 ms 64996 KB Output is correct
5 Correct 27 ms 64944 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 111924 KB Output is correct
2 Correct 1654 ms 120724 KB Output is correct
3 Correct 1574 ms 112584 KB Output is correct
4 Correct 1788 ms 121844 KB Output is correct
5 Correct 1735 ms 121888 KB Output is correct
6 Correct 24 ms 64972 KB Output is correct
7 Correct 1662 ms 112000 KB Output is correct
8 Correct 571 ms 133724 KB Output is correct
9 Correct 1690 ms 112000 KB Output is correct
10 Correct 1737 ms 121536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64924 KB Output is correct
2 Correct 60 ms 64996 KB Output is correct
3 Correct 864 ms 64980 KB Output is correct
4 Correct 24 ms 64996 KB Output is correct
5 Correct 27 ms 64944 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct
7 Correct 1664 ms 111924 KB Output is correct
8 Correct 1654 ms 120724 KB Output is correct
9 Correct 1574 ms 112584 KB Output is correct
10 Correct 1788 ms 121844 KB Output is correct
11 Correct 1735 ms 121888 KB Output is correct
12 Correct 24 ms 64972 KB Output is correct
13 Correct 1662 ms 112000 KB Output is correct
14 Correct 571 ms 133724 KB Output is correct
15 Correct 1690 ms 112000 KB Output is correct
16 Correct 1737 ms 121536 KB Output is correct
17 Correct 1996 ms 112000 KB Output is correct
18 Correct 1864 ms 112016 KB Output is correct
19 Correct 1885 ms 121588 KB Output is correct
20 Correct 1817 ms 112076 KB Output is correct
21 Correct 2003 ms 122180 KB Output is correct
22 Correct 1972 ms 122096 KB Output is correct
23 Correct 1877 ms 112000 KB Output is correct
24 Correct 796 ms 133792 KB Output is correct
25 Correct 1963 ms 112000 KB Output is correct
26 Correct 2029 ms 122096 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64924 KB Output is correct
2 Correct 60 ms 64996 KB Output is correct
3 Correct 864 ms 64980 KB Output is correct
4 Correct 24 ms 64996 KB Output is correct
5 Correct 27 ms 64944 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct
7 Correct 1664 ms 111924 KB Output is correct
8 Correct 1654 ms 120724 KB Output is correct
9 Correct 1574 ms 112584 KB Output is correct
10 Correct 1788 ms 121844 KB Output is correct
11 Correct 1735 ms 121888 KB Output is correct
12 Correct 24 ms 64972 KB Output is correct
13 Correct 1662 ms 112000 KB Output is correct
14 Correct 571 ms 133724 KB Output is correct
15 Correct 1690 ms 112000 KB Output is correct
16 Correct 1737 ms 121536 KB Output is correct
17 Correct 1996 ms 112000 KB Output is correct
18 Correct 1864 ms 112016 KB Output is correct
19 Correct 1885 ms 121588 KB Output is correct
20 Correct 1817 ms 112076 KB Output is correct
21 Correct 2003 ms 122180 KB Output is correct
22 Correct 1972 ms 122096 KB Output is correct
23 Correct 1877 ms 112000 KB Output is correct
24 Correct 796 ms 133792 KB Output is correct
25 Correct 1963 ms 112000 KB Output is correct
26 Correct 2029 ms 122096 KB Output is correct
27 Correct 8952 ms 111948 KB Output is correct
28 Correct 7800 ms 157656 KB Output is correct
29 Correct 8715 ms 176304 KB Output is correct
30 Correct 8140 ms 157144 KB Output is correct
31 Correct 8821 ms 185860 KB Output is correct
32 Correct 8889 ms 182020 KB Output is correct
33 Correct 1052 ms 187784 KB Output is correct
34 Correct 8902 ms 152640 KB Output is correct
35 Correct 8935 ms 178916 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64924 KB Output is correct
2 Correct 60 ms 64996 KB Output is correct
3 Correct 864 ms 64980 KB Output is correct
4 Correct 24 ms 64996 KB Output is correct
5 Correct 27 ms 64944 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct
7 Correct 1664 ms 111924 KB Output is correct
8 Correct 1654 ms 120724 KB Output is correct
9 Correct 1574 ms 112584 KB Output is correct
10 Correct 1788 ms 121844 KB Output is correct
11 Correct 1735 ms 121888 KB Output is correct
12 Correct 24 ms 64972 KB Output is correct
13 Correct 1662 ms 112000 KB Output is correct
14 Correct 571 ms 133724 KB Output is correct
15 Correct 1690 ms 112000 KB Output is correct
16 Correct 1737 ms 121536 KB Output is correct
17 Correct 1996 ms 112000 KB Output is correct
18 Correct 1864 ms 112016 KB Output is correct
19 Correct 1885 ms 121588 KB Output is correct
20 Correct 1817 ms 112076 KB Output is correct
21 Correct 2003 ms 122180 KB Output is correct
22 Correct 1972 ms 122096 KB Output is correct
23 Correct 1877 ms 112000 KB Output is correct
24 Correct 796 ms 133792 KB Output is correct
25 Correct 1963 ms 112000 KB Output is correct
26 Correct 2029 ms 122096 KB Output is correct
27 Correct 8952 ms 111948 KB Output is correct
28 Correct 7800 ms 157656 KB Output is correct
29 Correct 8715 ms 176304 KB Output is correct
30 Correct 8140 ms 157144 KB Output is correct
31 Correct 8821 ms 185860 KB Output is correct
32 Correct 8889 ms 182020 KB Output is correct
33 Correct 1052 ms 187784 KB Output is correct
34 Correct 8902 ms 152640 KB Output is correct
35 Correct 8935 ms 178916 KB Output is correct
36 Runtime error 561 ms 184596 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -