oj.uz

답안 #623663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623663 2022-08-06T09:02:50 Z valerikk Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 163184 KB 
#include "escape_route.h"
#include <algorithm>
#include <cassert>
#include <limits>

static const long long INF = 1e18;
static const int MAX_N = 91;
static const int MAX_M = 4006;

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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 59 ms 64980 KB Output is correct
3 Correct 850 ms 65004 KB Output is correct
4 Correct 24 ms 65044 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 32 ms 65020 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1654 ms 112376 KB Output is correct
2 Correct 1650 ms 121716 KB Output is correct
3 Correct 1588 ms 113680 KB Output is correct
4 Correct 1738 ms 122984 KB Output is correct
5 Correct 1749 ms 123064 KB Output is correct
6 Correct 25 ms 64972 KB Output is correct
7 Correct 1616 ms 112456 KB Output is correct
8 Correct 573 ms 134356 KB Output is correct
9 Correct 1686 ms 112656 KB Output is correct
10 Correct 1735 ms 123624 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 59 ms 64980 KB Output is correct
3 Correct 850 ms 65004 KB Output is correct
4 Correct 24 ms 65044 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 32 ms 65020 KB Output is correct
7 Correct 1654 ms 112376 KB Output is correct
8 Correct 1650 ms 121716 KB Output is correct
9 Correct 1588 ms 113680 KB Output is correct
10 Correct 1738 ms 122984 KB Output is correct
11 Correct 1749 ms 123064 KB Output is correct
12 Correct 25 ms 64972 KB Output is correct
13 Correct 1616 ms 112456 KB Output is correct
14 Correct 573 ms 134356 KB Output is correct
15 Correct 1686 ms 112656 KB Output is correct
16 Correct 1735 ms 123624 KB Output is correct
17 Correct 1978 ms 112332 KB Output is correct
18 Correct 1889 ms 112984 KB Output is correct
19 Correct 1878 ms 123516 KB Output is correct
20 Correct 1825 ms 112960 KB Output is correct
21 Correct 2013 ms 124104 KB Output is correct
22 Correct 2106 ms 124228 KB Output is correct
23 Correct 2065 ms 114768 KB Output is correct
24 Correct 856 ms 135764 KB Output is correct
25 Correct 1954 ms 113604 KB Output is correct
26 Correct 1998 ms 124464 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 59 ms 64980 KB Output is correct
3 Correct 850 ms 65004 KB Output is correct
4 Correct 24 ms 65044 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 32 ms 65020 KB Output is correct
7 Correct 1654 ms 112376 KB Output is correct
8 Correct 1650 ms 121716 KB Output is correct
9 Correct 1588 ms 113680 KB Output is correct
10 Correct 1738 ms 122984 KB Output is correct
11 Correct 1749 ms 123064 KB Output is correct
12 Correct 25 ms 64972 KB Output is correct
13 Correct 1616 ms 112456 KB Output is correct
14 Correct 573 ms 134356 KB Output is correct
15 Correct 1686 ms 112656 KB Output is correct
16 Correct 1735 ms 123624 KB Output is correct
17 Correct 1978 ms 112332 KB Output is correct
18 Correct 1889 ms 112984 KB Output is correct
19 Correct 1878 ms 123516 KB Output is correct
20 Correct 1825 ms 112960 KB Output is correct
21 Correct 2013 ms 124104 KB Output is correct
22 Correct 2106 ms 124228 KB Output is correct
23 Correct 2065 ms 114768 KB Output is correct
24 Correct 856 ms 135764 KB Output is correct
25 Correct 1954 ms 113604 KB Output is correct
26 Correct 1998 ms 124464 KB Output is correct
27 Correct 8976 ms 113484 KB Output is correct
28 Correct 8076 ms 134164 KB Output is correct
29 Correct 8662 ms 149236 KB Output is correct
30 Correct 8113 ms 134704 KB Output is correct
31 Correct 8742 ms 155508 KB Output is correct
32 Correct 8740 ms 155112 KB Output is correct
33 Correct 1006 ms 163184 KB Output is correct
34 Correct 8871 ms 127424 KB Output is correct
35 Correct 8851 ms 140320 KB Output is correct

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 64980 KB Output is correct
2 Correct 59 ms 64980 KB Output is correct
3 Correct 850 ms 65004 KB Output is correct
4 Correct 24 ms 65044 KB Output is correct
5 Correct 27 ms 64980 KB Output is correct
6 Correct 32 ms 65020 KB Output is correct
7 Correct 1654 ms 112376 KB Output is correct
8 Correct 1650 ms 121716 KB Output is correct
9 Correct 1588 ms 113680 KB Output is correct
10 Correct 1738 ms 122984 KB Output is correct
11 Correct 1749 ms 123064 KB Output is correct
12 Correct 25 ms 64972 KB Output is correct
13 Correct 1616 ms 112456 KB Output is correct
14 Correct 573 ms 134356 KB Output is correct
15 Correct 1686 ms 112656 KB Output is correct
16 Correct 1735 ms 123624 KB Output is correct
17 Correct 1978 ms 112332 KB Output is correct
18 Correct 1889 ms 112984 KB Output is correct
19 Correct 1878 ms 123516 KB Output is correct
20 Correct 1825 ms 112960 KB Output is correct
21 Correct 2013 ms 124104 KB Output is correct
22 Correct 2106 ms 124228 KB Output is correct
23 Correct 2065 ms 114768 KB Output is correct
24 Correct 856 ms 135764 KB Output is correct
25 Correct 1954 ms 113604 KB Output is correct
26 Correct 1998 ms 124464 KB Output is correct
27 Correct 8976 ms 113484 KB Output is correct
28 Correct 8076 ms 134164 KB Output is correct
29 Correct 8662 ms 149236 KB Output is correct
30 Correct 8113 ms 134704 KB Output is correct
31 Correct 8742 ms 155508 KB Output is correct
32 Correct 8740 ms 155112 KB Output is correct
33 Correct 1006 ms 163184 KB Output is correct
34 Correct 8871 ms 127424 KB Output is correct
35 Correct 8851 ms 140320 KB Output is correct
36 Execution timed out 9067 ms 120908 KB Time limit exceeded
37 Halted 0 ms 0 KB -