제출 #108476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108476		E869120	Golf (JOI17_golf)	C++14	30 / 100	2571 ms	452852 KiB

golf

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70