oj.uz

Submission #163416

# Submission time Handle Problem Language Result Execution time Memory
163416 2019-11-13T08:53:30 Z iefnah06 Soccer (JOI17_soccer) C++11
100 / 100
 1189 ms 154600 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXH = 510;
const int MAXS = MAXH * MAXH;
const int MAXV = 5 * MAXS;
const int MAXN = 100010;

const int INF = 1e6;
const ll DINF = 4e18;

int X, Y, N;
ll A, B, C;
int S, V;
int P[MAXN], Q[MAXN];

vector<int> vx[MAXH], vy[MAXH];

int inds[5][MAXH][MAXH];
int mincost[MAXH][MAXH];

const int mx[] = {1, 0, -1, 0};
const int my[] = {0, 1, 0, -1};

vector<pair<int, ll>> adj[MAXV];
ll dist[MAXV];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> X >> Y; X++, Y++;
	cin >> A >> B >> C;
	S = X * Y;
	V = 5 * S;
	cin >> N;
	vector<pair<int, int>> s;
	for (int x = 0; x < X; x++) {
		for (int y = 0; y < Y; y++) {
			mincost[x][y] = INF;
		}
	}
	for (int i = 0; i < N; i++) {
		int x, y; cin >> x >> y;
		P[i] = x, Q[i] = y;
		if (mincost[x][y] == INF) {
			s.emplace_back(x, y);
			mincost[x][y] = 0;
		}
	}
	for (size_t i = 0; i < s.size(); i++) {
		int x, y; tie(x, y) = s[i];
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + mx[dir], ny = y + my[dir];
			if (nx < 0 || nx >= X || ny < 0 || ny >= Y) continue;
			if (mincost[nx][ny] != INF) continue;
			mincost[nx][ny] = mincost[x][y] + 1;
			s.emplace_back(nx, ny);
		}
	}

	for (int cur = 0, i = 0; i < 5; i++) {
		for (int x = 0; x < X; x++) {
			for (int y = 0; y < Y; y++) {
				inds[i][x][y] = cur;
				cur++;
			}
		}
	}

	auto add_edge = [&](int a, int b, ll c) -> void {
		adj[a].emplace_back(b, c);
	};

	for (int x = 0; x < X; x++) {
		for (int y = 0; y < Y; y++) {
			for (int dir = 0; dir < 4; dir++) {
				int nx = x + mx[dir], ny = y + my[dir];
				if (nx < 0 || nx >= X || ny < 0 || ny >= Y) continue;
				add_edge(inds[4][x][y], inds[4][nx][ny], C);
			}
		}
	}

	for (int x = 0; x < X; x++) {
		for (int y = 0; y < Y; y++) {
			for (int dir = 0; dir < 4; dir++) {
				if (mincost[x][y] != INF) {
					add_edge(inds[dir][x][y], inds[4][x][y], C * mincost[x][y] + B);
				}
				int nx = x + mx[dir], ny = y + my[dir];
				if (nx < 0 || nx >= X || ny < 0 || ny >= Y) continue;
				add_edge(inds[4][x][y], inds[dir][nx][ny], A);
			}
		}
	}

	for (int x = 0; x < X; x++) {
		for (int y = 0; y < Y; y++) {
			for (int dir = 0; dir < 4; dir++) {
				int nx = x + mx[dir], ny = y + my[dir];
				if (nx < 0 || nx >= X || ny < 0 || ny >= Y) continue;
				add_edge(inds[dir][x][y], inds[dir][nx][ny], A);
			}
		}
	}

	set<pair<ll, int>> q;
	q.emplace(0, inds[4][P[0]][Q[0]]);
	for (int v = 0; v < V; v++) {
		dist[v] = DINF;
	}
	dist[inds[4][P[0]][Q[0]]] = 0;
	int dest = inds[4][P[N-1]][Q[N-1]];
	while (!q.empty()) {
		ll d; int cur; tie(d, cur) = *q.begin();
		q.erase(q.begin());
		if (cur == dest) {
			cout << d << '\n';
			return 0;
		}
		for (auto& e : adj[cur]) {
			int nxt; ll w; tie(nxt, w) = e;
			if (d + w < dist[nxt]) {
				q.erase(make_pair(dist[nxt], nxt));
				dist[nxt] = d + w;
				q.emplace(dist[nxt], nxt);
			}
		}
	}
	assert(false);

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 61420 KB Output is correct
2 Correct 33 ms 31096 KB Output is correct
3 Correct 563 ms 148148 KB Output is correct
4 Correct 451 ms 144184 KB Output is correct
5 Correct 260 ms 72688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 144644 KB Output is correct
2 Correct 418 ms 142316 KB Output is correct
3 Correct 546 ms 127328 KB Output is correct
4 Correct 806 ms 147524 KB Output is correct
5 Correct 587 ms 128744 KB Output is correct
6 Correct 673 ms 151400 KB Output is correct
7 Correct 636 ms 151772 KB Output is correct
8 Correct 620 ms 153064 KB Output is correct
9 Correct 495 ms 146320 KB Output is correct
10 Correct 144 ms 55872 KB Output is correct
11 Correct 801 ms 154600 KB Output is correct
12 Correct 829 ms 153940 KB Output is correct
13 Correct 600 ms 128324 KB Output is correct
14 Correct 556 ms 149608 KB Output is correct
15 Correct 338 ms 120808 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 61420 KB Output is correct
2 Correct 33 ms 31096 KB Output is correct
3 Correct 563 ms 148148 KB Output is correct
4 Correct 451 ms 144184 KB Output is correct
5 Correct 260 ms 72688 KB Output is correct
6 Correct 467 ms 144644 KB Output is correct
7 Correct 418 ms 142316 KB Output is correct
8 Correct 546 ms 127328 KB Output is correct
9 Correct 806 ms 147524 KB Output is correct
10 Correct 587 ms 128744 KB Output is correct
11 Correct 673 ms 151400 KB Output is correct
12 Correct 636 ms 151772 KB Output is correct
13 Correct 620 ms 153064 KB Output is correct
14 Correct 495 ms 146320 KB Output is correct
15 Correct 144 ms 55872 KB Output is correct
16 Correct 801 ms 154600 KB Output is correct
17 Correct 829 ms 153940 KB Output is correct
18 Correct 600 ms 128324 KB Output is correct
19 Correct 556 ms 149608 KB Output is correct
20 Correct 338 ms 120808 KB Output is correct
21 Correct 201 ms 72444 KB Output is correct
22 Correct 1084 ms 147536 KB Output is correct
23 Correct 1143 ms 135192 KB Output is correct
24 Correct 916 ms 145512 KB Output is correct
25 Correct 1012 ms 151204 KB Output is correct
26 Correct 1037 ms 147540 KB Output is correct
27 Correct 634 ms 140648 KB Output is correct
28 Correct 949 ms 140876 KB Output is correct
29 Correct 1189 ms 145416 KB Output is correct
30 Correct 668 ms 140736 KB Output is correct
31 Correct 614 ms 148756 KB Output is correct
32 Correct 764 ms 149772 KB Output is correct
33 Correct 768 ms 151196 KB Output is correct
34 Correct 461 ms 142104 KB Output is correct
35 Correct 834 ms 140788 KB Output is correct