Submission #1227091

#TimeUsernameProblemLanguageResultExecution timeMemory
1227091chaeryeongSoccer (JOI17_soccer)C++20
100 / 100
818 ms44400 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
int h, w;
ll A, B, C;
int n;
ll a[100001][2];
ll dist[502][502]; //person at (i, j)
ll dist2[502][502][4]; //ball with persons at (i, j) and being shot
ll dist3[502][502]; //nobody at (i, j)
ll dist4[502][502][4]; //ball alone at (i, j) and being shot
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
bool check (int x, int y) {
	return x >= 0 && x <= h && y >= 0 && y <= w;
}
ll mn[502][502];
void solve () {
	cin >> h >> w >> A >> B >> C;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0] >> a[i][1];
	}
	memset(mn, -1, sizeof(mn));
	queue <pair <int, int>> cur;
	for (int i = 1; i <= n; i++) {
		if (mn[a[i][0]][a[i][1]] != -1) {
			continue;
		}
		cur.push({a[i][0], a[i][1]});
		mn[a[i][0]][a[i][1]] = 0;
	}
	while (!cur.empty()) {
		auto [x, y] = cur.front();
		cur.pop();
		for (int i = 0; i < 4; i++) {
			if (check(x + dx[i], y + dy[i])) {
				if (mn[x + dx[i]][y + dy[i]] == -1) {
					mn[x + dx[i]][y + dy[i]] = mn[x][y] + 1;
					cur.push({x + dx[i], y + dy[i]});
				}
			}
		}
	}
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			dist[i][j] = dist3[i][j] = inf;
			for (int k = 0; k < 4; k++) {
				dist2[i][j][k] = dist4[i][j][k] = inf;
			}
		}
	}
	priority_queue <array <ll, 5>, vector <array <ll, 5>>, greater <>> pq;
	auto relax = [&] (array <ll, 5> x) -> void {
		if (x[4] == 1) {
			if (x[0] < dist[x[1]][x[2]]) {
				dist[x[1]][x[2]] = x[0];
				pq.push(x);
			}
 		} else if (x[4] == 2) {
 			if (x[0] < dist2[x[1]][x[2]][x[3]]) {
 				pq.push(x);
 				dist2[x[1]][x[2]][x[3]] = x[0];
 			}
 		} else if (x[4] == 3) {
 			if (x[0] < dist3[x[1]][x[2]]) {
 				dist3[x[1]][x[2]] = x[0];
 				pq.push(x);
 			}
 		} else {
 			if (x[0] < dist4[x[1]][x[2]][x[3]]) {
 				pq.push(x);
 				dist4[x[1]][x[2]][x[3]] = x[0];
 			}
 		}
 	};
 	relax({0, a[1][0], a[1][1], -1, 1});
	while (!pq.empty()) {
		auto x = pq.top();
		pq.pop();
		if (x[4] == 1) {
			if (x[0] > dist[x[1]][x[2]]) {
				continue;
			}
			for (int i = 0; i < 4; i++) {
				if (check(x[1] + dx[i], x[2] + dy[i])) {
					relax({x[0] + C, x[1] + dx[i], x[2] + dy[i], -1, 1});
				}
			}
			relax({x[0], x[1], x[2], -1, 3});
			for (auto i : {0, 1, 2, 3}) {
				relax({x[0] + B, x[1], x[2], i, 2});
				relax({x[0] + B, x[1], x[2], i, 4});
			}
 		} else if (x[4] == 2) {
 			if (x[0] > dist2[x[1]][x[2]][x[3]]) {
 				continue;
 			}
 			if (x[3] == 0 && check(x[1] - 1, x[2])) {
 				relax({x[0] + A + C, x[1] - 1, x[2], x[3], 2});
 			}
  			if (x[3] == 1 && check(x[1] + 1, x[2])) {
 				relax({x[0] + A + C, x[1] + 1, x[2], x[3], 2});
 			}
 			if (x[3] == 2 && check(x[1], x[2] - 1)) {
 				relax({x[0] + A + C, x[1], x[2] - 1, x[3], 2});
 			}
  			if (x[3] == 3 && check(x[1], x[2] + 1)) {
 				relax({x[0] + A + C, x[1], x[2] + 1, x[3], 2});
 			}
 			relax({x[0], x[1], x[2], -1, 1});
 		} else if (x[4] == 3) {
 			if (x[0] > dist3[x[1]][x[2]]) {
 				continue;
 			}
			relax({x[0] + C * mn[x[1]][x[2]], x[1], x[2], -1, 1});
 		} else {
 			if (x[0] > dist4[x[1]][x[2]][x[3]]) {
 				continue;
 			}
 			if (x[3] == 0 && check(x[1] - 1, x[2])) {
 				relax({x[0] + A, x[1] - 1, x[2], x[3], 4});
 			}
  			if (x[3] == 1 && check(x[1] + 1, x[2])) {
 				relax({x[0] + A, x[1] + 1, x[2], x[3], 4});
 			}
 			if (x[3] == 2 && check(x[1], x[2] - 1)) {
 				relax({x[0] + A, x[1], x[2] - 1, x[3], 4});
 			}
  			if (x[3] == 3 && check(x[1], x[2] + 1)) {
 				relax({x[0] + A, x[1], x[2] + 1, x[3], 4});
 			}
 			relax({x[0], x[1], x[2], -1, 3});
 		}
	}
	cout << min(dist[a[n][0]][a[n][1]], dist3[a[n][0]][a[n][1]]) << '\n';
}	
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...