oj.uz

Submission #590122

# Submission time Handle Problem Language Result Execution time Memory
590122 2022-07-05T14:36:56 Z dutinmeow Soccer (JOI17_soccer) C++17
100 / 100
 620 ms 117120 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e15;
const array<int, 4> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};

int main() {
	int N, M, Q;
	long long A, B, C;
	cin >> N >> M >> A >> B >> C >> Q;
	N++, M++;

	vector<int> X(Q), Y(Q);
	queue<pair<int, int>> que;
	vector<vector<long long>> bfs(N, vector<long long>(M, INF));
	for (int i = 0; i < Q; i++) {
		int x, y;
		cin >> x >> y;
		que.emplace(x, y);
		bfs[x][y] = 0;
		X[i] = x, Y[i] = y;
	}
	while (!que.empty()) {
		auto [x, y] = que.front(); que.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k], ny = y + dy[k];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && bfs[nx][ny] == INF) {
				bfs[nx][ny] = bfs[x][y] + 1;
				que.emplace(nx, ny);
			}
		}
	}

	int n = 0;
	vector<vector<int>> nM(N, vector<int>(M)), nX(N, vector<int>(M)), nY(N, vector<int>(M));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			nM[i][j] = n++;
			nX[i][j] = n++;
			nY[i][j] = n++;
		}
	}

	vector<vector<pair<int, long long>>> G(n);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			G[nM[i][j]].emplace_back(nX[i][j], B);
			G[nM[i][j]].emplace_back(nY[i][j], B);
			G[nX[i][j]].emplace_back(nM[i][j], C * bfs[i][j]);
			G[nY[i][j]].emplace_back(nM[i][j], C * bfs[i][j]);
		}
	}
	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			G[nM[i][j]].emplace_back(nM[i + 1][j], C);
			G[nM[i + 1][j]].emplace_back(nM[i][j], C);
			G[nX[i][j]].emplace_back(nX[i + 1][j], A);
			G[nX[i + 1][j]].emplace_back(nX[i][j], A);
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M - 1; j++) {
			G[nM[i][j]].emplace_back(nM[i][j + 1], C);
			G[nM[i][j + 1]].emplace_back(nM[i][j], C);
			G[nY[i][j]].emplace_back(nY[i][j + 1], A);
			G[nY[i][j + 1]].emplace_back(nY[i][j], A);
		}
	}

	using pq_node = pair<long long, int>;
	priority_queue<pq_node, vector<pq_node>, greater<pq_node>> pq;
	vector<long long> dis(n, INF);

	pq.emplace(0, nM[X[0]][Y[0]]);
	dis[nM[X[0]][Y[0]]] = 0;
	while (!pq.empty()) {
		auto [d, u] = pq.top(); pq.pop();
		for (auto [v, w] : G[u]) {
			if (d + w < dis[v]) {
				dis[v] = d + w;
				pq.emplace(dis[v], v);
			}
		}
	}

	cout << min({dis[nM[X[Q - 1]][Y[Q - 1]]], dis[nX[X[Q - 1]][Y[Q - 1]]], dis[nY[X[Q - 1]][Y[Q - 1]]]}) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 28208 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 580 ms 115500 KB Output is correct
4 Correct 546 ms 115476 KB Output is correct
5 Correct 126 ms 41020 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 115608 KB Output is correct
2 Correct 609 ms 115544 KB Output is correct
3 Correct 396 ms 93320 KB Output is correct
4 Correct 355 ms 115476 KB Output is correct
5 Correct 367 ms 93436 KB Output is correct
6 Correct 402 ms 115512 KB Output is correct
7 Correct 497 ms 115652 KB Output is correct
8 Correct 465 ms 115516 KB Output is correct
9 Correct 521 ms 115516 KB Output is correct
10 Correct 60 ms 19392 KB Output is correct
11 Correct 500 ms 115648 KB Output is correct
12 Correct 497 ms 115508 KB Output is correct
13 Correct 300 ms 93424 KB Output is correct
14 Correct 536 ms 115548 KB Output is correct
15 Correct 401 ms 93404 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 28208 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 580 ms 115500 KB Output is correct
4 Correct 546 ms 115476 KB Output is correct
5 Correct 126 ms 41020 KB Output is correct
6 Correct 501 ms 115608 KB Output is correct
7 Correct 609 ms 115544 KB Output is correct
8 Correct 396 ms 93320 KB Output is correct
9 Correct 355 ms 115476 KB Output is correct
10 Correct 367 ms 93436 KB Output is correct
11 Correct 402 ms 115512 KB Output is correct
12 Correct 497 ms 115652 KB Output is correct
13 Correct 465 ms 115516 KB Output is correct
14 Correct 521 ms 115516 KB Output is correct
15 Correct 60 ms 19392 KB Output is correct
16 Correct 500 ms 115648 KB Output is correct
17 Correct 497 ms 115508 KB Output is correct
18 Correct 300 ms 93424 KB Output is correct
19 Correct 536 ms 115548 KB Output is correct
20 Correct 401 ms 93404 KB Output is correct
21 Correct 140 ms 40572 KB Output is correct
22 Correct 615 ms 115624 KB Output is correct
23 Correct 553 ms 102416 KB Output is correct
24 Correct 602 ms 113472 KB Output is correct
25 Correct 531 ms 115700 KB Output is correct
26 Correct 551 ms 115676 KB Output is correct
27 Correct 428 ms 112688 KB Output is correct
28 Correct 463 ms 112984 KB Output is correct
29 Correct 530 ms 114936 KB Output is correct
30 Correct 395 ms 112956 KB Output is correct
31 Correct 582 ms 115600 KB Output is correct
32 Correct 620 ms 117120 KB Output is correct
33 Correct 401 ms 115516 KB Output is correct
34 Correct 595 ms 115580 KB Output is correct
35 Correct 341 ms 112864 KB Output is correct