oj.uz

Submission #623655

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

static const long long INF = 1e18;
static const int MAX_N = 60;
static const int MAX_M = 1770;

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 + 1][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) {
						stop = std::min(stop, std::max(stops.back(), c[u][v] - dist[u] - l[u][v] + 1));
					}
				}
			}
			std::copy(dist, dist + N, dists[(int) stops.size() - 1]);
			stops.push_back(stop);
			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 25 ms 65000 KB Output is correct
2 Correct 60 ms 64928 KB Output is correct
3 Correct 892 ms 65092 KB Output is correct
4 Correct 25 ms 65040 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 26 ms 64936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1639 ms 111992 KB Output is correct
2 Correct 1663 ms 120952 KB Output is correct
3 Correct 1615 ms 112676 KB Output is correct
4 Correct 1747 ms 122104 KB Output is correct
5 Correct 1741 ms 122104 KB Output is correct
6 Correct 24 ms 64916 KB Output is correct
7 Correct 1656 ms 112064 KB Output is correct
8 Correct 540 ms 133856 KB Output is correct
9 Correct 1668 ms 112076 KB Output is correct
10 Correct 1746 ms 121592 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65000 KB Output is correct
2 Correct 60 ms 64928 KB Output is correct
3 Correct 892 ms 65092 KB Output is correct
4 Correct 25 ms 65040 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 26 ms 64936 KB Output is correct
7 Correct 1639 ms 111992 KB Output is correct
8 Correct 1663 ms 120952 KB Output is correct
9 Correct 1615 ms 112676 KB Output is correct
10 Correct 1747 ms 122104 KB Output is correct
11 Correct 1741 ms 122104 KB Output is correct
12 Correct 24 ms 64916 KB Output is correct
13 Correct 1656 ms 112064 KB Output is correct
14 Correct 540 ms 133856 KB Output is correct
15 Correct 1668 ms 112076 KB Output is correct
16 Correct 1746 ms 121592 KB Output is correct
17 Correct 1995 ms 112076 KB Output is correct
18 Correct 1895 ms 111972 KB Output is correct
19 Correct 1891 ms 121648 KB Output is correct
20 Correct 1844 ms 111996 KB Output is correct
21 Correct 1990 ms 122220 KB Output is correct
22 Correct 2015 ms 122112 KB Output is correct
23 Correct 1892 ms 112076 KB Output is correct
24 Correct 779 ms 133724 KB Output is correct
25 Correct 1949 ms 112152 KB Output is correct
26 Correct 2005 ms 122308 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65000 KB Output is correct
2 Correct 60 ms 64928 KB Output is correct
3 Correct 892 ms 65092 KB Output is correct
4 Correct 25 ms 65040 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 26 ms 64936 KB Output is correct
7 Correct 1639 ms 111992 KB Output is correct
8 Correct 1663 ms 120952 KB Output is correct
9 Correct 1615 ms 112676 KB Output is correct
10 Correct 1747 ms 122104 KB Output is correct
11 Correct 1741 ms 122104 KB Output is correct
12 Correct 24 ms 64916 KB Output is correct
13 Correct 1656 ms 112064 KB Output is correct
14 Correct 540 ms 133856 KB Output is correct
15 Correct 1668 ms 112076 KB Output is correct
16 Correct 1746 ms 121592 KB Output is correct
17 Correct 1995 ms 112076 KB Output is correct
18 Correct 1895 ms 111972 KB Output is correct
19 Correct 1891 ms 121648 KB Output is correct
20 Correct 1844 ms 111996 KB Output is correct
21 Correct 1990 ms 122220 KB Output is correct
22 Correct 2015 ms 122112 KB Output is correct
23 Correct 1892 ms 112076 KB Output is correct
24 Correct 779 ms 133724 KB Output is correct
25 Correct 1949 ms 112152 KB Output is correct
26 Correct 2005 ms 122308 KB Output is correct
27 Execution timed out 9089 ms 112128 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65000 KB Output is correct
2 Correct 60 ms 64928 KB Output is correct
3 Correct 892 ms 65092 KB Output is correct
4 Correct 25 ms 65040 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 26 ms 64936 KB Output is correct
7 Correct 1639 ms 111992 KB Output is correct
8 Correct 1663 ms 120952 KB Output is correct
9 Correct 1615 ms 112676 KB Output is correct
10 Correct 1747 ms 122104 KB Output is correct
11 Correct 1741 ms 122104 KB Output is correct
12 Correct 24 ms 64916 KB Output is correct
13 Correct 1656 ms 112064 KB Output is correct
14 Correct 540 ms 133856 KB Output is correct
15 Correct 1668 ms 112076 KB Output is correct
16 Correct 1746 ms 121592 KB Output is correct
17 Correct 1995 ms 112076 KB Output is correct
18 Correct 1895 ms 111972 KB Output is correct
19 Correct 1891 ms 121648 KB Output is correct
20 Correct 1844 ms 111996 KB Output is correct
21 Correct 1990 ms 122220 KB Output is correct
22 Correct 2015 ms 122112 KB Output is correct
23 Correct 1892 ms 112076 KB Output is correct
24 Correct 779 ms 133724 KB Output is correct
25 Correct 1949 ms 112152 KB Output is correct
26 Correct 2005 ms 122308 KB Output is correct
27 Execution timed out 9089 ms 112128 KB Time limit exceeded
28 Halted 0 ms 0 KB -