oj.uz

Submission #108476

# Submission time Handle Problem Language Result Execution time Memory
108476 2019-04-30T04:31:57 Z E869120 Golf (JOI17_golf) C++14
30 / 100
 2571 ms 452852 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
#pragma warning (disable: 4996)

int N, sx, sy, gx, gy, px[1009], qx[1009], py[1009], qy[1009], r[4099][4099], dist[4099][4099][5];
vector<int>X, Y;
queue<tuple<int, int, int>>Q[10000];

int solve() {
	for (int i = 0; i <= X.size() * 2; i++) { for (int j = 0; j <= Y.size() * 2; j++) { for (int k = 0; k < 5; k++) dist[i][j][k] = (1 << 30); } }

	int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };

	dist[sx][sy][4] = 0; Q[0].push(make_tuple(sx, sy, 4));
	for (int i = 0; i < 8000; i++) {
		while (!Q[i].empty()) {
			int cx = get<0>(Q[i].front()), cy = get<1>(Q[i].front()), dir = get<2>(Q[i].front()); Q[i].pop();

			// 停止する場合
			if (dir != 4 && dist[cx][cy][4] > dist[cx][cy][dir]) {
				dist[cx][cy][4] = dist[cx][cy][dir];
				Q[dist[cx][cy][4]].push(make_tuple(cx, cy, 4));
			}

			// そのままの向きに動く場合
			int ex = cx + dx[dir], ey = cy + dy[dir];
			if (ex >= 0 && ey >= 0 && ex <= X.size() * 2 && ey <= Y.size() * 2 && r[ex][ey] == 0 && dist[ex][ey][dir] > dist[cx][cy][dir]) {
				dist[ex][ey][dir] = dist[cx][cy][dir];
				Q[dist[ex][ey][dir]].push(make_tuple(ex, ey, dir));
			}

			// 動き出す場合
			if (dir == 4) {
				for (int j = 0; j < 4; j++) {
					if (dist[cx][cy][j] > dist[cx][cy][dir] + 1) {
						dist[cx][cy][j] = dist[cx][cy][dir] + 1;
						Q[dist[cx][cy][j]].push(make_tuple(cx, cy, j));
					}
				}
			}
		}
	}
	return dist[gx][gy][4];
}

int main() {
	cin >> sx >> sy >> gx >> gy >> N;
	X.push_back(sx); X.push_back(gx);
	Y.push_back(sy); Y.push_back(gy);
	for (int i = 1; i <= N; i++) {
		cin >> px[i] >> qx[i] >> py[i] >> qy[i];
		X.push_back(px[i]); X.push_back(qx[i]);
		Y.push_back(py[i]); Y.push_back(qy[i]);
	}
	sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for (int i = 1; i <= N; i++) {
		px[i] = lower_bound(X.begin(), X.end(), px[i]) - X.begin();
		qx[i] = lower_bound(X.begin(), X.end(), qx[i]) - X.begin();
		py[i] = lower_bound(Y.begin(), Y.end(), py[i]) - Y.begin();
		qy[i] = lower_bound(Y.begin(), Y.end(), qy[i]) - Y.begin();
		r[px[i] * 2 + 1][py[i] * 2 + 1]++;
		r[px[i] * 2 + 1][qy[i] * 2]--;
		r[qx[i] * 2][py[i] * 2 + 1]--;
		r[qx[i] * 2][qy[i] * 2]++;
	}
	sx = lower_bound(X.begin(), X.end(), sx) - X.begin(); sx *= 2;
	sy = lower_bound(Y.begin(), Y.end(), sy) - Y.begin(); sy *= 2;
	gx = lower_bound(X.begin(), X.end(), gx) - X.begin(); gx *= 2;
	gy = lower_bound(Y.begin(), Y.end(), gy) - Y.begin(); gy *= 2;
	for (int i = 0; i <= X.size() * 2; i++) {
		for (int j = 1; j <= Y.size() * 2; j++) r[i][j] += r[i][j - 1];
	}
	for (int i = 0; i <= Y.size() * 2; i++) {
		for (int j = 1; j <= X.size() * 2; j++) r[j][i] += r[j - 1][i];
	}

	cout << solve() << endl;
	return 0;
}

Compilation message

golf.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
golf.cpp: In function 'int solve()':
golf.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= X.size() * 2; i++) { for (int j = 0; j <= Y.size() * 2; j++) { for (int k = 0; k < 5; k++) dist[i][j][k] = (1 << 30); } }
                  ~~^~~~~~~~~~~~~~~
golf.cpp:14:62: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= X.size() * 2; i++) { for (int j = 0; j <= Y.size() * 2; j++) { for (int k = 0; k < 5; k++) dist[i][j][k] = (1 << 30); } }
                                                            ~~^~~~~~~~~~~~~~~
golf.cpp:31:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ex >= 0 && ey >= 0 && ex <= X.size() * 2 && ey <= Y.size() * 2 && r[ex][ey] == 0 && dist[ex][ey][dir] > dist[cx][cy][dir]) {
                              ~~~^~~~~~~~~~~~~~~
golf.cpp:31:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ex >= 0 && ey >= 0 && ex <= X.size() * 2 && ey <= Y.size() * 2 && r[ex][ey] == 0 && dist[ex][ey][dir] > dist[cx][cy][dir]) {
                                                    ~~~^~~~~~~~~~~~~~~
golf.cpp: In function 'int main()':
golf.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= X.size() * 2; i++) {
                  ~~^~~~~~~~~~~~~~~
golf.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j <= Y.size() * 2; j++) r[i][j] += r[i][j - 1];
                   ~~^~~~~~~~~~~~~~~
golf.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= Y.size() * 2; i++) {
                  ~~^~~~~~~~~~~~~~~
golf.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j <= X.size() * 2; j++) r[j][i] += r[j - 1][i];
                   ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7040 KB Output is correct
2 Correct 10 ms 7168 KB Output is correct
3 Correct 10 ms 7296 KB Output is correct
4 Correct 22 ms 13824 KB Output is correct
5 Correct 268 ms 89236 KB Output is correct
6 Correct 301 ms 89564 KB Output is correct
7 Correct 253 ms 84232 KB Output is correct
8 Correct 244 ms 91368 KB Output is correct
9 Correct 264 ms 85624 KB Output is correct
10 Correct 365 ms 90616 KB Output is correct
11 Correct 288 ms 95680 KB Output is correct
12 Correct 265 ms 87416 KB Output is correct
13 Correct 237 ms 89208 KB Output is correct
14 Correct 272 ms 92024 KB Output is correct
15 Correct 87 ms 29484 KB Output is correct
16 Correct 335 ms 83064 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7040 KB Output is correct
2 Correct 10 ms 7168 KB Output is correct
3 Correct 10 ms 7296 KB Output is correct
4 Correct 22 ms 13824 KB Output is correct
5 Correct 268 ms 89236 KB Output is correct
6 Correct 301 ms 89564 KB Output is correct
7 Correct 253 ms 84232 KB Output is correct
8 Correct 244 ms 91368 KB Output is correct
9 Correct 264 ms 85624 KB Output is correct
10 Correct 365 ms 90616 KB Output is correct
11 Correct 288 ms 95680 KB Output is correct
12 Correct 265 ms 87416 KB Output is correct
13 Correct 237 ms 89208 KB Output is correct
14 Correct 272 ms 92024 KB Output is correct
15 Correct 87 ms 29484 KB Output is correct
16 Correct 335 ms 83064 KB Output is correct
17 Correct 1983 ms 443360 KB Output is correct
18 Correct 2336 ms 444052 KB Output is correct
19 Correct 1701 ms 432240 KB Output is correct
20 Correct 1819 ms 439404 KB Output is correct
21 Correct 2571 ms 452852 KB Output is correct
22 Correct 1955 ms 448884 KB Output is correct
23 Correct 1760 ms 436560 KB Output is correct
24 Correct 1569 ms 435284 KB Output is correct
25 Correct 1675 ms 449032 KB Output is correct
26 Correct 1707 ms 426376 KB Output is correct
27 Correct 140 ms 37480 KB Output is correct
28 Correct 422 ms 97272 KB Output is correct
29 Correct 423 ms 99576 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7040 KB Output is correct
2 Correct 10 ms 7168 KB Output is correct
3 Correct 10 ms 7296 KB Output is correct
4 Correct 22 ms 13824 KB Output is correct
5 Correct 268 ms 89236 KB Output is correct
6 Correct 301 ms 89564 KB Output is correct
7 Correct 253 ms 84232 KB Output is correct
8 Correct 244 ms 91368 KB Output is correct
9 Correct 264 ms 85624 KB Output is correct
10 Correct 365 ms 90616 KB Output is correct
11 Correct 288 ms 95680 KB Output is correct
12 Correct 265 ms 87416 KB Output is correct
13 Correct 237 ms 89208 KB Output is correct
14 Correct 272 ms 92024 KB Output is correct
15 Correct 87 ms 29484 KB Output is correct
16 Correct 335 ms 83064 KB Output is correct
17 Correct 1983 ms 443360 KB Output is correct
18 Correct 2336 ms 444052 KB Output is correct
19 Correct 1701 ms 432240 KB Output is correct
20 Correct 1819 ms 439404 KB Output is correct
21 Correct 2571 ms 452852 KB Output is correct
22 Correct 1955 ms 448884 KB Output is correct
23 Correct 1760 ms 436560 KB Output is correct
24 Correct 1569 ms 435284 KB Output is correct
25 Correct 1675 ms 449032 KB Output is correct
26 Correct 1707 ms 426376 KB Output is correct
27 Correct 140 ms 37480 KB Output is correct
28 Correct 422 ms 97272 KB Output is correct
29 Correct 423 ms 99576 KB Output is correct
30 Runtime error 35 ms 13944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -