Submission #772310

#	Time	Username	Problem	Language	Result	Execution time	Memory
772310		Asamai	Soccer (JOI17_soccer)	C++17	100 / 100	379 ms	24436 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}

#define     all(a)                a.begin(), a.end()
#define     pb                    push_back
#define     pf                    push_front
#define     fi                    first
#define     se                    second
#define     int                   long long

typedef     long long             ll;
typedef     unsigned long long    ull;
typedef     double                db;
typedef     long double           ld;
typedef     pair<db, db>          pdb;
typedef     pair<ld, ld>          pld;
typedef     pair<int, int>        pii;
typedef     pair<ll, ll>          pll;
typedef     pair<ll, int>         plli;
typedef     pair<int, ll>         pill;

const int MAX_N = 1e5 + 5;
const int MAX_M = 500 + 5;
const ll inf = 1e18 + 1;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int h, w;
int n;
int A, B, C;
pii s[MAX_N];
int nearestPlayer[MAX_M][MAX_M];
int ball[MAX_M][MAX_M][4];
int player[MAX_M][MAX_M];
queue<pii> q;

bool inside(int x, int y) {
	return ~x && ~y && x <= h && y <= w;
}

bool inside(pii x) {
	return ~x.fi && ~x.se && x.fi <= h && x.se <= w;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> h >> w >> A >> B >> C >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i].fi >> s[i].se;
		nearestPlayer[s[i].fi][s[i].se] = 1;
		q.push(s[i]);
	}

	while (!q.empty()) {
		pii u = q.front();
		q.pop();

		for (int k = 0; k < 4; k++) {
			pii v = {u.fi + dx[k], u.se + dy[k]};
			if (inside(v) && !nearestPlayer[v.fi][v.se]) {
				nearestPlayer[v.fi][v.se] = nearestPlayer[u.fi][u.se] + 1;
				q.push(v);
			}
		}
	}

	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			nearestPlayer[i][j]--;
			nearestPlayer[i][j] *= C;
			player[i][j] = inf;
			for (int k = 0; k < 4; k++) {
				ball[i][j][k] = inf;
			}
		}
	}

	priority_queue<pair<int, pair<pii, int>>, vector<pair<int, pair<pii, int>>>, greater<pair<int, pair<pii, int>>>> pq;
	player[s[1].fi][s[1].se] = 0;
	pq.push({0, {s[1], 4}});

	while (!pq.empty()) {
		int currW = pq.top().fi;
		pii u = pq.top().se.fi;
		int dir = pq.top().se.se;

		pq.pop();

		if (dir == 4) {
			if (currW > player[u.fi][u.se]) {
				continue;
			}

			for (int k = 0; k < 4; k++) {
				if (currW + B < ball[u.fi][u.se][k]) {
					ball[u.fi][u.se][k] = currW + B;
					pq.push({ball[u.fi][u.se][k], {u, k}});
				}

				pii v = {u.fi + dx[k], u.se + dy[k]};
				if (!inside(v)) continue;
				if (currW + C < player[v.fi][v.se]) {
					player[v.fi][v.se] = currW + C;
					pq.push({player[v.fi][v.se], {v, 4}});
				}
			}
		}
		else {
			if (currW > ball[u.fi][u.se][dir]) {
				continue;
			}

			pii v = {u.fi + dx[dir], u.se + dy[dir]};
			if (inside(v)) {
				if (currW + A < ball[v.fi][v.se][dir]) {
					ball[v.fi][v.se][dir] = currW + A;
					pq.push({ball[v.fi][v.se][dir], {v, dir}});
				}
			}

			if (currW + nearestPlayer[u.fi][u.se] < player[u.fi][u.se]) {
				player[u.fi][u.se] = currW + nearestPlayer[u.fi][u.se];
				pq.push({player[u.fi][u.se], {u, 4}});
			}
		}
	}

	int ans = inf;
	for (int k = 0; k < 4; k++) {
		minimize(ans, ball[s[n].fi][s[n].se][k]);
	}
	minimize(ans, player[s[n].fi][s[n].se]);
	cout << ans;

	return 0;
}

/*


*/

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65