Submission #141078

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
141078	2019-08-06T14:59:18 Z	DrumpfTheGodEmperor	Soccer (JOI17_soccer)	C++14	100 / 100	460 ms	26856 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	16496 KB	Output is correct
2	Correct	15 ms	14456 KB	Output is correct
3	Correct	142 ms	22704 KB	Output is correct
4	Correct	71 ms	18668 KB	Output is correct
5	Correct	84 ms	14520 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	18740 KB	Output is correct
2	Correct	50 ms	16684 KB	Output is correct
3	Correct	195 ms	22656 KB	Output is correct
4	Correct	375 ms	22640 KB	Output is correct
5	Correct	207 ms	22816 KB	Output is correct
6	Correct	251 ms	22772 KB	Output is correct
7	Correct	150 ms	22892 KB	Output is correct
8	Correct	165 ms	22720 KB	Output is correct
9	Correct	38 ms	15692 KB	Output is correct
10	Correct	35 ms	16616 KB	Output is correct
11	Correct	285 ms	23032 KB	Output is correct
12	Correct	270 ms	22748 KB	Output is correct
13	Correct	199 ms	22768 KB	Output is correct
14	Correct	129 ms	22880 KB	Output is correct
15	Correct	32 ms	15732 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	16496 KB	Output is correct
2	Correct	15 ms	14456 KB	Output is correct
3	Correct	142 ms	22704 KB	Output is correct
4	Correct	71 ms	18668 KB	Output is correct
5	Correct	84 ms	14520 KB	Output is correct
6	Correct	70 ms	18740 KB	Output is correct
7	Correct	50 ms	16684 KB	Output is correct
8	Correct	195 ms	22656 KB	Output is correct
9	Correct	375 ms	22640 KB	Output is correct
10	Correct	207 ms	22816 KB	Output is correct
11	Correct	251 ms	22772 KB	Output is correct
12	Correct	150 ms	22892 KB	Output is correct
13	Correct	165 ms	22720 KB	Output is correct
14	Correct	38 ms	15692 KB	Output is correct
15	Correct	35 ms	16616 KB	Output is correct
16	Correct	285 ms	23032 KB	Output is correct
17	Correct	270 ms	22748 KB	Output is correct
18	Correct	199 ms	22768 KB	Output is correct
19	Correct	129 ms	22880 KB	Output is correct
20	Correct	32 ms	15732 KB	Output is correct
21	Correct	52 ms	15000 KB	Output is correct
22	Correct	377 ms	22720 KB	Output is correct
23	Correct	456 ms	18660 KB	Output is correct
24	Correct	352 ms	18920 KB	Output is correct
25	Correct	307 ms	22952 KB	Output is correct
26	Correct	400 ms	23136 KB	Output is correct
27	Correct	238 ms	18040 KB	Output is correct
28	Correct	370 ms	19064 KB	Output is correct
29	Correct	460 ms	22556 KB	Output is correct
30	Correct	190 ms	18552 KB	Output is correct
31	Correct	113 ms	18840 KB	Output is correct
32	Correct	234 ms	26856 KB	Output is correct
33	Correct	286 ms	22792 KB	Output is correct
34	Correct	64 ms	16724 KB	Output is correct
35	Correct	278 ms	18296 KB	Output is correct