oj.uz

Submission #670482

# Submission time Handle Problem Language Result Execution time Memory
670482 2022-12-09T08:28:20 Z Sohsoh84 Soccer (JOI17_soccer) C++17
100 / 100
 555 ms 231232 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pair<pll, int>> PX;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 2e3 + 10;

ll n, m, A, B, C, k, p_dist[MAXN][MAXN], SX, SY, TX, TY, dist[MAXN][MAXN][6];
queue<pll> q;
priority_queue<PX, vector<PX>, greater<PX>> pq;

inline void add_p(int x, int y, ll d) {
	if (x < 0 || y < 0 || x > n || y > m || p_dist[x][y] <= d) return;
	p_dist[x][y] = d;
	q.push({x, y});
}

inline void add(int x, int y, int b, ll d) {
	if (x < 0 || y < 0 || x > n || y > m || dist[x][y][b] <= d) return;
	dist[x][y][b] = d;
	pq.push({d, {{x, y}, b}});
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> A >> B >> C >> k;

	memset(p_dist, 63, sizeof p_dist);
	for (int i = 1; i < k; i++) {
		int x, y;
		cin >> x >> y;
		if (i == 1) SX = x, SY = y;
		add_p(x, y, 0);
	}

	cin >> TX >> TY;
	while (!q.empty()) {
		auto [x, y] = q.front();
		q.pop();
		ll d = p_dist[x][y];

		add_p(x - 1, y, d + 1);
		add_p(x + 1, y, d + 1);
		add_p(x, y - 1, d + 1);
		add_p(x, y + 1, d + 1);
	}

	memset(dist, 63, sizeof dist);
	add(SX, SY, 0, 0);

	while (!pq.empty()) {
		ll d = pq.top().X, x = pq.top().Y.X.X, y = pq.top().Y.X.Y, b = pq.top().Y.Y;
		pq.pop();
		if (d != dist[x][y][b]) continue;
	
		if (!b) {
			add(x, y, 1, d + p_dist[x][y] * C);
			continue;
		}

		if (b == 1) {
			add(x, y, 0, d);	
			add(x, y, 2, d + B);	
			add(x, y, 3, d + B);	
			add(x, y, 4, d + B);	
			add(x, y, 5, d + B);	
			add(x + 1, y, 1, d + C);
			add(x - 1, y, 1, d + C);
			add(x, y + 1, 1, d + C);
			add(x, y - 1, 1, d + C);
			continue;
		}

		add(x, y, 0, d);
		if (b == 2) add(x - 1, y, b, d + A);
		if (b == 3) add(x, y - 1, b, d + A);
		if (b == 4) add(x + 1, y, b, d + A);
		if (b == 5) add(x, y + 1, b, d + A);
	}

	cout << dist[TX][TY][0] << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 223816 KB Output is correct
2 Correct 80 ms 221736 KB Output is correct
3 Correct 360 ms 229924 KB Output is correct
4 Correct 366 ms 230028 KB Output is correct
5 Correct 156 ms 221756 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 230064 KB Output is correct
2 Correct 427 ms 230084 KB Output is correct
3 Correct 343 ms 230000 KB Output is correct
4 Correct 330 ms 229952 KB Output is correct
5 Correct 351 ms 229984 KB Output is correct
6 Correct 349 ms 229948 KB Output is correct
7 Correct 437 ms 230100 KB Output is correct
8 Correct 388 ms 230064 KB Output is correct
9 Correct 458 ms 230196 KB Output is correct
10 Correct 137 ms 223884 KB Output is correct
11 Correct 434 ms 230072 KB Output is correct
12 Correct 442 ms 230048 KB Output is correct
13 Correct 284 ms 230028 KB Output is correct
14 Correct 465 ms 230192 KB Output is correct
15 Correct 360 ms 230192 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 223816 KB Output is correct
2 Correct 80 ms 221736 KB Output is correct
3 Correct 360 ms 229924 KB Output is correct
4 Correct 366 ms 230028 KB Output is correct
5 Correct 156 ms 221756 KB Output is correct
6 Correct 453 ms 230064 KB Output is correct
7 Correct 427 ms 230084 KB Output is correct
8 Correct 343 ms 230000 KB Output is correct
9 Correct 330 ms 229952 KB Output is correct
10 Correct 351 ms 229984 KB Output is correct
11 Correct 349 ms 229948 KB Output is correct
12 Correct 437 ms 230100 KB Output is correct
13 Correct 388 ms 230064 KB Output is correct
14 Correct 458 ms 230196 KB Output is correct
15 Correct 137 ms 223884 KB Output is correct
16 Correct 434 ms 230072 KB Output is correct
17 Correct 442 ms 230048 KB Output is correct
18 Correct 284 ms 230028 KB Output is correct
19 Correct 465 ms 230192 KB Output is correct
20 Correct 360 ms 230192 KB Output is correct
21 Correct 181 ms 222344 KB Output is correct
22 Correct 503 ms 230048 KB Output is correct
23 Correct 473 ms 225964 KB Output is correct
24 Correct 554 ms 226288 KB Output is correct
25 Correct 425 ms 230040 KB Output is correct
26 Correct 485 ms 230412 KB Output is correct
27 Correct 346 ms 223896 KB Output is correct
28 Correct 345 ms 224236 KB Output is correct
29 Correct 432 ms 227348 KB Output is correct
30 Correct 301 ms 223644 KB Output is correct
31 Correct 444 ms 230228 KB Output is correct
32 Correct 532 ms 231232 KB Output is correct
33 Correct 354 ms 230072 KB Output is correct
34 Correct 555 ms 230228 KB Output is correct
35 Correct 287 ms 222872 KB Output is correct