Submission #141078

#	Time	Username	Problem	Language	Result	Execution time	Memory
141078		DrumpfTheGodEmperor	Soccer (JOI17_soccer)	C++14	100 / 100	460 ms	26856 KiB

soccer

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, ii> iii;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 1e5 + 5, BOARD = 505;
int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
int h, w, a, b, c, n, s[N], t[N], nearest[BOARD][BOARD], ans[BOARD][BOARD][6];
queue<pair<int, int>> bfsQueue;
priority_queue<iii, vector<iii>, greater<iii>> pq;
bool check(int i, int j) {
	return i >= 0 && j >= 0 && i < h && j < w;
}
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> w >> a >> b >> c >> n;
	h++, w++;
	memset(nearest, 63, sizeof nearest);
	memset(ans, 63, sizeof ans);
	fw (i, 0, n) {
		cin >> s[i] >> t[i];
		nearest[s[i]][t[i]] = 0;
		bfsQueue.push(ii(s[i], t[i]));
	}
	while (!bfsQueue.empty()) {
		ii curCoords = bfsQueue.front(); bfsQueue.pop();
		int curI = curCoords.fi, curJ = curCoords.se;
		fw (i, 0, 4) {
			int nxtI = curI + dx[i], nxtJ = curJ + dy[i];
			if (!check(nxtI, nxtJ)) continue;
			if (nearest[nxtI][nxtJ] <= nearest[curI][curJ] + 1) continue;
//			cout << "Fix " << nxtI << " " << nxtJ << " old nearest = " << nearest[nxtI][nxtJ] << " cur nearest = " << nearest[curI][curJ] << "\n";
			nearest[nxtI][nxtJ] = nearest[curI][curJ] + 1;
			bfsQueue.push(make_pair(nxtI, nxtJ));
		}
	}
	//A player will never pick up a ball twice.
	//If the ball is at (i, j), it can be assumed the nearest player came and picked it up.
	//0, 1, 2, 3: current direction. 4: someone is holding the ball. 5: no one is holding the ball.
	ans[s[0]][t[0]][4] = 0;
	pq.push(iii(ii(0, 4), ii(s[0], t[0])));
	while (!pq.empty()) {
		iii tmp = pq.top(); pq.pop();
		int curI = tmp.se.fi, curJ = tmp.se.se;
		int curCost = tmp.fi.fi, data = tmp.fi.se;
		if (curCost != ans[curI][curJ][data]) continue;
		if (curI == s[n - 1] && curJ == t[n - 1]) {
			cout << curCost << "\n";
			return 0;
		}
		if (data == 5) {
			if (ans[curI][curJ][5] + c * nearest[curI][curJ] < ans[curI][curJ][4]) {
				ans[curI][curJ][4] = ans[curI][curJ][5] + c * nearest[curI][curJ];
				pq.push(iii(ii(ans[curI][curJ][4], 4), ii(curI, curJ)));
			}
		} else if (data == 4) {
			fw (direction, 0, 4) {
				int nxtI = curI + dx[direction], nxtJ = curJ + dy[direction];
				if (!check(nxtI, nxtJ)) continue;
				if (ans[curI][curJ][4] + c < ans[nxtI][nxtJ][4]) {
					ans[nxtI][nxtJ][4] = ans[curI][curJ][4] + c;
					pq.push(iii(ii(ans[nxtI][nxtJ][4], 4), ii(nxtI, nxtJ)));
				}
				//Move in direction
			}
			fw (direction, 0, 4) {
				//Kick ball to direction
				if (ans[curI][curJ][4] + b < ans[curI][curJ][direction]) {
					ans[curI][curJ][direction] = ans[curI][curJ][4] + b;
					pq.push(iii(ii(ans[curI][curJ][direction], direction), ii(curI, curJ)));
				}
			}
		} else {
			//Keep moving in direction
			int direction = data;
			int nxtI = curI + dx[direction], nxtJ = curJ + dy[direction];
			if (check(nxtI, nxtJ)) {
				if (ans[curI][curJ][direction] + a < ans[nxtI][nxtJ][direction]) {
					ans[nxtI][nxtJ][direction] = ans[curI][curJ][direction] + a;
					pq.push(iii(ii(ans[nxtI][nxtJ][direction], direction), ii(nxtI, nxtJ)));
				}
			}
			//Stop at current position
			if (ans[curI][curJ][direction] < ans[curI][curJ][5]) {
				ans[curI][curJ][5] = ans[curI][curJ][direction];
				pq.push(iii(ii(ans[curI][curJ][5], 5), ii(curI, curJ)));
			}
		}
	}
//	cout << ans[1][2][2] << " " << ans[1][4][5] << " " << ans[1][4][4] << "\n";
	return 0;
}

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