oj.uz

Submission #1031905

# Submission time Handle Problem Language Result Execution time Memory
1031905 2024-07-23T08:36:08 Z 정민찬(#10962) Golf (JOI17_golf) C++17
0 / 100
 3 ms 4956 KB 
#include <bits/stdc++.h>

using namespace std;

int board[1010][1010];
int dist[1010][1010][4];
int vis[1010][1010][4];

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

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	int s, t, u, v;
	cin >> s >> t >> u >> v;
	int n;
	cin >> n;
	vector<array<int,4>> a(n);
	vector<int> X = {s, u}, Y = {t, v};
	for (int i=0; i<n; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
		X.push_back(a[i][0]);
		X.push_back(a[i][1]);
		Y.push_back(a[i][2]);
		Y.push_back(a[i][3]);
	}
	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=0; i<n; i++) {
		a[i][0] = lower_bound(X.begin(), X.end(), a[i][0]) - X.begin() + 1;
		a[i][1] = lower_bound(X.begin(), X.end(), a[i][1]) - X.begin() + 1;
		a[i][2] = lower_bound(Y.begin(), Y.end(), a[i][2]) - Y.begin() + 1;
		a[i][3] = lower_bound(Y.begin(), Y.end(), a[i][3]) - Y.begin() + 1;
	}
	s = lower_bound(X.begin(), X.end(), s) - X.begin() + 1;
	u = lower_bound(X.begin(), X.end(), u) - X.begin() + 1;
	t = lower_bound(Y.begin(), Y.end(), t) - Y.begin() + 1;
	v = lower_bound(Y.begin(), Y.end(), v) - Y.begin() + 1;
	s *= 2; u *= 2; t *= 2; v *= 2;
	for (int i=0; i<n; i++) {
		for (int x=a[i][0]*2+1; x<=a[i][1]*2-1; x++) {
			for (int y=a[i][2]*2+1; y<=a[i][3]*2-1; y++) {
				board[x][y] = 1;
			}
		}
	}
	int mX = X.size() * 2 + 2;
	int mY = Y.size() * 2 + 2;
	deque<array<int,4>> dq;
	for (int i=0; i<4; i++) {
		dq.push_back({s, t, i, 1});
		dist[s][t][i] = 0;
	}
	while (!dq.empty()) {
		int x = dq.front()[0];
		int y = dq.front()[1];
		int dir = dq.front()[2];
		int cost = dq.front()[3];
		dq.pop_front();
		if (vis[x][y][dir]) continue;
		vis[x][y][dir] = 1;
		if (x == u && y == v) {
			cout << cost << '\n';
			break;
		}
		for (int k=0; k<4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx < 0 || nx > mX || ny < 0 || ny > mY) continue;
			if (board[nx][ny]) continue;
			if (k == dir) {
				dq.push_front({nx, ny, k, cost});
			}
			else {
				dq.push_back({nx, ny, k, cost+1});
			}
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Runtime error 2 ms 2396 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Runtime error 2 ms 2396 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Runtime error 2 ms 2396 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -