oj.uz

Submission #623661

# Submission time Handle Problem Language Result Execution time Memory
623661 2022-08-06T08:58:00 Z valerikk Escape Route (JOI21_escape_route) C++17
35 / 100
 2016 ms 145320 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[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 25 ms 64980 KB Output is correct
2 Correct 59 ms 64984 KB Output is correct
3 Correct 837 ms 64944 KB Output is correct
4 Correct 28 ms 65112 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 27 ms 65044 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1632 ms 111876 KB Output is correct
2 Correct 1635 ms 120968 KB Output is correct
3 Correct 1583 ms 112600 KB Output is correct
4 Correct 1743 ms 121968 KB Output is correct
5 Correct 1733 ms 122080 KB Output is correct
6 Correct 24 ms 64944 KB Output is correct
7 Correct 1605 ms 112068 KB Output is correct
8 Correct 579 ms 133876 KB Output is correct
9 Correct 1661 ms 112116 KB Output is correct
10 Correct 1729 ms 121592 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64980 KB Output is correct
2 Correct 59 ms 64984 KB Output is correct
3 Correct 837 ms 64944 KB Output is correct
4 Correct 28 ms 65112 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 27 ms 65044 KB Output is correct
7 Correct 1632 ms 111876 KB Output is correct
8 Correct 1635 ms 120968 KB Output is correct
9 Correct 1583 ms 112600 KB Output is correct
10 Correct 1743 ms 121968 KB Output is correct
11 Correct 1733 ms 122080 KB Output is correct
12 Correct 24 ms 64944 KB Output is correct
13 Correct 1605 ms 112068 KB Output is correct
14 Correct 579 ms 133876 KB Output is correct
15 Correct 1661 ms 112116 KB Output is correct
16 Correct 1729 ms 121592 KB Output is correct
17 Correct 1980 ms 112032 KB Output is correct
18 Correct 1865 ms 112052 KB Output is correct
19 Correct 1903 ms 121836 KB Output is correct
20 Correct 1827 ms 112132 KB Output is correct
21 Correct 1982 ms 122388 KB Output is correct
22 Correct 1960 ms 122216 KB Output is correct
23 Correct 1869 ms 112076 KB Output is correct
24 Correct 814 ms 133848 KB Output is correct
25 Correct 1958 ms 112168 KB Output is correct
26 Correct 2016 ms 122172 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64980 KB Output is correct
2 Correct 59 ms 64984 KB Output is correct
3 Correct 837 ms 64944 KB Output is correct
4 Correct 28 ms 65112 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 27 ms 65044 KB Output is correct
7 Correct 1632 ms 111876 KB Output is correct
8 Correct 1635 ms 120968 KB Output is correct
9 Correct 1583 ms 112600 KB Output is correct
10 Correct 1743 ms 121968 KB Output is correct
11 Correct 1733 ms 122080 KB Output is correct
12 Correct 24 ms 64944 KB Output is correct
13 Correct 1605 ms 112068 KB Output is correct
14 Correct 579 ms 133876 KB Output is correct
15 Correct 1661 ms 112116 KB Output is correct
16 Correct 1729 ms 121592 KB Output is correct
17 Correct 1980 ms 112032 KB Output is correct
18 Correct 1865 ms 112052 KB Output is correct
19 Correct 1903 ms 121836 KB Output is correct
20 Correct 1827 ms 112132 KB Output is correct
21 Correct 1982 ms 122388 KB Output is correct
22 Correct 1960 ms 122216 KB Output is correct
23 Correct 1869 ms 112076 KB Output is correct
24 Correct 814 ms 133848 KB Output is correct
25 Correct 1958 ms 112168 KB Output is correct
26 Correct 2016 ms 122172 KB Output is correct
27 Runtime error 249 ms 145320 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64980 KB Output is correct
2 Correct 59 ms 64984 KB Output is correct
3 Correct 837 ms 64944 KB Output is correct
4 Correct 28 ms 65112 KB Output is correct
5 Correct 27 ms 64984 KB Output is correct
6 Correct 27 ms 65044 KB Output is correct
7 Correct 1632 ms 111876 KB Output is correct
8 Correct 1635 ms 120968 KB Output is correct
9 Correct 1583 ms 112600 KB Output is correct
10 Correct 1743 ms 121968 KB Output is correct
11 Correct 1733 ms 122080 KB Output is correct
12 Correct 24 ms 64944 KB Output is correct
13 Correct 1605 ms 112068 KB Output is correct
14 Correct 579 ms 133876 KB Output is correct
15 Correct 1661 ms 112116 KB Output is correct
16 Correct 1729 ms 121592 KB Output is correct
17 Correct 1980 ms 112032 KB Output is correct
18 Correct 1865 ms 112052 KB Output is correct
19 Correct 1903 ms 121836 KB Output is correct
20 Correct 1827 ms 112132 KB Output is correct
21 Correct 1982 ms 122388 KB Output is correct
22 Correct 1960 ms 122216 KB Output is correct
23 Correct 1869 ms 112076 KB Output is correct
24 Correct 814 ms 133848 KB Output is correct
25 Correct 1958 ms 112168 KB Output is correct
26 Correct 2016 ms 122172 KB Output is correct
27 Runtime error 249 ms 145320 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -