oj.uz

답안 #623656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623656 2022-08-06T08:47:50 Z valerikk Escape Route (JOI21_escape_route) C++17
35 / 100
 2024 ms 145216 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) {
						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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 65024 KB Output is correct
2 Correct 62 ms 65036 KB Output is correct
3 Correct 866 ms 65008 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 26 ms 64980 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1629 ms 111892 KB Output is correct
2 Correct 1627 ms 120948 KB Output is correct
3 Correct 1572 ms 112636 KB Output is correct
4 Correct 1764 ms 121940 KB Output is correct
5 Correct 1748 ms 122192 KB Output is correct
6 Correct 23 ms 64980 KB Output is correct
7 Correct 1606 ms 111988 KB Output is correct
8 Correct 487 ms 133748 KB Output is correct
9 Correct 1663 ms 111948 KB Output is correct
10 Correct 1741 ms 121516 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 65024 KB Output is correct
2 Correct 62 ms 65036 KB Output is correct
3 Correct 866 ms 65008 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 26 ms 64980 KB Output is correct
7 Correct 1629 ms 111892 KB Output is correct
8 Correct 1627 ms 120948 KB Output is correct
9 Correct 1572 ms 112636 KB Output is correct
10 Correct 1764 ms 121940 KB Output is correct
11 Correct 1748 ms 122192 KB Output is correct
12 Correct 23 ms 64980 KB Output is correct
13 Correct 1606 ms 111988 KB Output is correct
14 Correct 487 ms 133748 KB Output is correct
15 Correct 1663 ms 111948 KB Output is correct
16 Correct 1741 ms 121516 KB Output is correct
17 Correct 2024 ms 111948 KB Output is correct
18 Correct 1914 ms 111952 KB Output is correct
19 Correct 1893 ms 121552 KB Output is correct
20 Correct 1843 ms 111888 KB Output is correct
21 Correct 2015 ms 122200 KB Output is correct
22 Correct 2013 ms 122120 KB Output is correct
23 Correct 1934 ms 111980 KB Output is correct
24 Correct 738 ms 133772 KB Output is correct
25 Correct 1955 ms 112104 KB Output is correct
26 Correct 1998 ms 122148 KB Output is correct

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 65024 KB Output is correct
2 Correct 62 ms 65036 KB Output is correct
3 Correct 866 ms 65008 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 26 ms 64980 KB Output is correct
7 Correct 1629 ms 111892 KB Output is correct
8 Correct 1627 ms 120948 KB Output is correct
9 Correct 1572 ms 112636 KB Output is correct
10 Correct 1764 ms 121940 KB Output is correct
11 Correct 1748 ms 122192 KB Output is correct
12 Correct 23 ms 64980 KB Output is correct
13 Correct 1606 ms 111988 KB Output is correct
14 Correct 487 ms 133748 KB Output is correct
15 Correct 1663 ms 111948 KB Output is correct
16 Correct 1741 ms 121516 KB Output is correct
17 Correct 2024 ms 111948 KB Output is correct
18 Correct 1914 ms 111952 KB Output is correct
19 Correct 1893 ms 121552 KB Output is correct
20 Correct 1843 ms 111888 KB Output is correct
21 Correct 2015 ms 122200 KB Output is correct
22 Correct 2013 ms 122120 KB Output is correct
23 Correct 1934 ms 111980 KB Output is correct
24 Correct 738 ms 133772 KB Output is correct
25 Correct 1955 ms 112104 KB Output is correct
26 Correct 1998 ms 122148 KB Output is correct
27 Runtime error 257 ms 145216 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 65024 KB Output is correct
2 Correct 62 ms 65036 KB Output is correct
3 Correct 866 ms 65008 KB Output is correct
4 Correct 28 ms 64972 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 26 ms 64980 KB Output is correct
7 Correct 1629 ms 111892 KB Output is correct
8 Correct 1627 ms 120948 KB Output is correct
9 Correct 1572 ms 112636 KB Output is correct
10 Correct 1764 ms 121940 KB Output is correct
11 Correct 1748 ms 122192 KB Output is correct
12 Correct 23 ms 64980 KB Output is correct
13 Correct 1606 ms 111988 KB Output is correct
14 Correct 487 ms 133748 KB Output is correct
15 Correct 1663 ms 111948 KB Output is correct
16 Correct 1741 ms 121516 KB Output is correct
17 Correct 2024 ms 111948 KB Output is correct
18 Correct 1914 ms 111952 KB Output is correct
19 Correct 1893 ms 121552 KB Output is correct
20 Correct 1843 ms 111888 KB Output is correct
21 Correct 2015 ms 122200 KB Output is correct
22 Correct 2013 ms 122120 KB Output is correct
23 Correct 1934 ms 111980 KB Output is correct
24 Correct 738 ms 133772 KB Output is correct
25 Correct 1955 ms 112104 KB Output is correct
26 Correct 1998 ms 122148 KB Output is correct
27 Runtime error 257 ms 145216 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -