oj.uz

Submission #681914

# Submission time Handle Problem Language Result Execution time Memory
681914 2023-01-14T21:02:59 Z Kahou Soccer (JOI17_soccer) C++14
100 / 100
 681 ms 30932 KB 
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll inf = 1e18 + 50;
const int N = 550, M = 1e5 + 50;
ll n, h, w, A, B, C;
pll P[M];
ll dis[N][N][6], bdis[N][N];
queue<pll> q;
set<pll> st;
int dx[] = {0, 1, 0,-1};
int dy[] = {1, 0,-1, 0};


inline ll f(int x, int y, int c) {
	return x*N*6 + y*6 + c;
}

bool val(int x, int y) {
	return x >= 0 && x <= h && y >= 0 && y <= w;
}

void solve() {
	cin >> h >> w;
	cin >> A >> B >> C;
	cin >> n;
	for (int x = 0; x <= h; x++) {
		for (int y = 0; y <= w; y++) {
			bdis[x][y] = inf;
			for (int c = 0; c < 6; c++) {
				dis[x][y][c] = inf;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> P[i].F >> P[i].S;
		if (i < n) {
			bdis[P[i].F][P[i].S] = 0;
			q.push(P[i]);
		}
	}

	if (n == 1) {
		cout << 0 << endl;
		return;
	}

	while (q.size()) {
		int x = q.front().F, y = q.front().S;
		q.pop();
		for (int i = 0; i < 4; i++) {
			if (val(x+dx[i], y+dy[i]) && bdis[x][y]+C < bdis[x+dx[i]][y+dy[i]]) {
				bdis[x+dx[i]][y+dy[i]] = bdis[x][y]+C;
				q.push({x+dx[i], y+dy[i]});
			}
		}
	}
	dis[P[1].F][P[1].S][5] = 0;
	st.insert({0, f(P[1].F, P[1].S, 5)});
	while (st.size()) {
		ll x = st.begin()->S/(N*6), y = (st.begin()->S/6)%N, c = (st.begin()->S%6);
		st.erase(st.begin());
		if (c == 0) {
			if (dis[x][y][0] + bdis[x][y] < dis[x][y][5]) {
				st.erase({dis[x][y][5], f(x, y, 5)});
				dis[x][y][5] = dis[x][y][0] + bdis[x][y];
				st.insert({dis[x][y][5], f(x, y, 5)});
			}
		}
		else if (c == 5) {
			if (dis[x][y][5] < dis[x][y][0]) {
				st.erase({dis[x][y][0], f(x, y, 0)});
				dis[x][y][0] = dis[x][y][5];
				st.insert({dis[x][y][0], f(x, y, 0)});
			}
			for (int i = 0; i < 4; i++) {
				if (dis[x][y][5] + B < dis[x][y][i+1]) {
					st.erase({dis[x][y][i+1], f(x, y, i+1)});
					dis[x][y][i+1] = dis[x][y][5] + B;
					st.insert({dis[x][y][i+1], f(x, y, i+1)});
				}
				ll xp = x+dx[i], yp = y+dy[i];
				if (!val(xp, yp)) continue;
				if (dis[x][y][5] + C < dis[xp][yp][5]) {
					st.erase({dis[xp][yp][5], f(xp, yp, 5)});
					dis[xp][yp][5] = dis[x][y][5] + C;
					st.insert({dis[xp][yp][5], f(xp, yp, 5)});
				}
			}
		}
		else {
			if (dis[x][y][c] < dis[x][y][0]) {
				st.erase({dis[x][y][0], f(x, y, 0)});
				dis[x][y][0] = dis[x][y][c];
				st.insert({dis[x][y][0], f(x, y, 0)});
			}
			ll xp = x+dx[c-1], yp = y+dy[c-1];
			if (!val(xp, yp)) continue;
			if (dis[x][y][c] + A < dis[xp][yp][c]) {
				st.erase({dis[xp][yp][c], f(xp, yp, c)});
				dis[xp][yp][c] = dis[x][y][c] + A;
				st.insert({dis[xp][yp][c], f(xp, yp, c)});
			}
		}
	}
	cout << dis[P[n].F][P[n].S][0] << endl;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7988 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 365 ms 25276 KB Output is correct
4 Correct 414 ms 26820 KB Output is correct
5 Correct 85 ms 7664 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 28832 KB Output is correct
2 Correct 368 ms 29452 KB Output is correct
3 Correct 258 ms 22356 KB Output is correct
4 Correct 245 ms 23796 KB Output is correct
5 Correct 286 ms 23712 KB Output is correct
6 Correct 240 ms 27700 KB Output is correct
7 Correct 485 ms 30924 KB Output is correct
8 Correct 361 ms 30796 KB Output is correct
9 Correct 396 ms 30548 KB Output is correct
10 Correct 55 ms 9132 KB Output is correct
11 Correct 413 ms 30792 KB Output is correct
12 Correct 402 ms 30060 KB Output is correct
13 Correct 202 ms 23108 KB Output is correct
14 Correct 431 ms 30932 KB Output is correct
15 Correct 319 ms 26316 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 7988 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 365 ms 25276 KB Output is correct
4 Correct 414 ms 26820 KB Output is correct
5 Correct 85 ms 7664 KB Output is correct
6 Correct 470 ms 28832 KB Output is correct
7 Correct 368 ms 29452 KB Output is correct
8 Correct 258 ms 22356 KB Output is correct
9 Correct 245 ms 23796 KB Output is correct
10 Correct 286 ms 23712 KB Output is correct
11 Correct 240 ms 27700 KB Output is correct
12 Correct 485 ms 30924 KB Output is correct
13 Correct 361 ms 30796 KB Output is correct
14 Correct 396 ms 30548 KB Output is correct
15 Correct 55 ms 9132 KB Output is correct
16 Correct 413 ms 30792 KB Output is correct
17 Correct 402 ms 30060 KB Output is correct
18 Correct 202 ms 23108 KB Output is correct
19 Correct 431 ms 30932 KB Output is correct
20 Correct 319 ms 26316 KB Output is correct
21 Correct 90 ms 7980 KB Output is correct
22 Correct 681 ms 23848 KB Output is correct
23 Correct 552 ms 20684 KB Output is correct
24 Correct 583 ms 21332 KB Output is correct
25 Correct 484 ms 27384 KB Output is correct
26 Correct 544 ms 24060 KB Output is correct
27 Correct 302 ms 19048 KB Output is correct
28 Correct 306 ms 20052 KB Output is correct
29 Correct 468 ms 22648 KB Output is correct
30 Correct 220 ms 19500 KB Output is correct
31 Correct 499 ms 30872 KB Output is correct
32 Correct 568 ms 30464 KB Output is correct
33 Correct 336 ms 27628 KB Output is correct
34 Correct 555 ms 27276 KB Output is correct
35 Correct 243 ms 19472 KB Output is correct