oj.uz

Submission #36531

# Submission time Handle Problem Language Result Execution time Memory
36531 2017-12-10T09:17:44 Z cheater2k Soccer (JOI17_soccer) C++14
100 / 100
 439 ms 23288 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 505;
const long long inf = 1e18;
const int dx[] = {0, 0, -1, +1}, dy[] = {-1, +1, 0, 0};

int n, H, W, A, B, C;
int endX, endY;
int d[N][N];
long long f[N][N][5];

struct State {
	long long dist; int x; int y; int dir;
	// dir == 4: the ball is currently kept by a player
	State(long long dist=0, int x=0, int y=0, int dir=0): dist(dist), x(x), y(y), dir(dir) {}
	bool operator < (const State &rhs) const {
		return dist > rhs.dist;
	}
};
priority_queue <State> pq;
queue < pair<int,int> > q;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> H >> W; // [0 -> H, 0 -> W]
	cin >> A >> B >> C;

	// PREPARE
	for (int x = 0; x <= H; ++x) {
		for (int y = 0; y <= W; ++y) {
			d[x][y] = -1; // minimum distance of (x,y) and a player
			for (int dir = 0; dir < 5; ++dir) f[x][y][dir] = inf; // for Dijkstra
		}
	}
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y; // the position of the i-th player	
		if (i == 1) {
			pq.push(State(0, x, y, 4));
			f[x][y][4] = 0;
		} else if (i == n) {
			endX = x; endY = y;
		}
		q.push(make_pair(x,y));
		d[x][y] = 0;
	}
	while(!q.empty()) {
		int x = q.front().first, y = q.front().second; q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir], ny = y + dy[dir];
			if (nx < 0 || nx > H || ny < 0 || ny > W || d[nx][ny] != -1) continue;
			d[nx][ny] = d[x][y] + 1;
			q.push(make_pair(nx,ny));
		}
	}	
	//------------------------------------------------------------------------------------

	// DIJKSTRA
	while(!pq.empty()) {
		State top = pq.top(); pq.pop();
		int x = top.x, y = top.y, dir = top.dir;
		if (f[x][y][dir] != top.dist) continue;
		if (x == endX && y == endY) return printf("%lld\n", top.dist), 0;

		int nx, ny; // next position

		if (dir == 4) {
			// kick the ball
			for (int ndir = 0; ndir < 4; ++ndir) {
				nx = x + dx[ndir], ny = y + dy[ndir];
				if (nx < 0 || nx > H || ny < 0 || ny > W) continue;
				if (f[nx][ny][ndir] > top.dist + A + B) {
					f[nx][ny][ndir] = top.dist + A + B;
					pq.push(State(f[nx][ny][ndir], nx, ny, ndir));
				}
			}
			// move the ball
			for (int ndir = 0; ndir < 4; ++ndir) {
				nx = x + dx[ndir], ny = y + dy[ndir];
				if (nx < 0 || nx > H || ny < 0 || ny > W) continue;
				if (f[nx][ny][4] > top.dist + C) {
					f[nx][ny][4] = top.dist + C;
					pq.push(State(f[nx][ny][4], nx, ny, 4));
				}
			}
		} else {
			// the ball keeps moving
			nx = x + dx[dir], ny = y + dy[dir];
			if (nx >= 0 && nx <= H && ny >= 0 && ny <= W && f[nx][ny][dir] > top.dist + A) {
				f[nx][ny][dir] = top.dist + A;
				pq.push(State(f[nx][ny][dir], nx, ny, dir));
			}
			// the ball stops and some player grabs it
			if (f[x][y][4] > top.dist + 1LL * C * d[x][y]) {
				f[x][y][4] = top.dist + 1LL * C * d[x][y];
				pq.push(State(f[x][y][4], x, y, 4));
			}
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15480 KB Output is correct
2 Correct 0 ms 13136 KB Output is correct
3 Correct 96 ms 22392 KB Output is correct
4 Correct 36 ms 17784 KB Output is correct
5 Correct 39 ms 13360 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17808 KB Output is correct
2 Correct 29 ms 15524 KB Output is correct
3 Correct 136 ms 22416 KB Output is correct
4 Correct 359 ms 22404 KB Output is correct
5 Correct 199 ms 22436 KB Output is correct
6 Correct 206 ms 22404 KB Output is correct
7 Correct 109 ms 22484 KB Output is correct
8 Correct 129 ms 22448 KB Output is correct
9 Correct 33 ms 15572 KB Output is correct
10 Correct 19 ms 15532 KB Output is correct
11 Correct 286 ms 22492 KB Output is correct
12 Correct 269 ms 22436 KB Output is correct
13 Correct 159 ms 22404 KB Output is correct
14 Correct 103 ms 22488 KB Output is correct
15 Correct 13 ms 14424 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 15480 KB Output is correct
2 Correct 0 ms 13136 KB Output is correct
3 Correct 96 ms 22392 KB Output is correct
4 Correct 36 ms 17784 KB Output is correct
5 Correct 39 ms 13360 KB Output is correct
6 Correct 46 ms 17808 KB Output is correct
7 Correct 29 ms 15524 KB Output is correct
8 Correct 136 ms 22416 KB Output is correct
9 Correct 359 ms 22404 KB Output is correct
10 Correct 199 ms 22436 KB Output is correct
11 Correct 206 ms 22404 KB Output is correct
12 Correct 109 ms 22484 KB Output is correct
13 Correct 129 ms 22448 KB Output is correct
14 Correct 33 ms 15572 KB Output is correct
15 Correct 19 ms 15532 KB Output is correct
16 Correct 286 ms 22492 KB Output is correct
17 Correct 269 ms 22436 KB Output is correct
18 Correct 159 ms 22404 KB Output is correct
19 Correct 103 ms 22488 KB Output is correct
20 Correct 13 ms 14424 KB Output is correct
21 Correct 16 ms 14352 KB Output is correct
22 Correct 339 ms 22416 KB Output is correct
23 Correct 439 ms 17832 KB Output is correct
24 Correct 289 ms 17972 KB Output is correct
25 Correct 256 ms 22420 KB Output is correct
26 Correct 329 ms 22580 KB Output is correct
27 Correct 113 ms 14196 KB Output is correct
28 Correct 223 ms 14344 KB Output is correct
29 Correct 389 ms 18548 KB Output is correct
30 Correct 116 ms 14064 KB Output is correct
31 Correct 73 ms 17876 KB Output is correct
32 Correct 166 ms 23288 KB Output is correct
33 Correct 226 ms 22396 KB Output is correct
34 Correct 33 ms 15576 KB Output is correct
35 Correct 169 ms 14064 KB Output is correct