oj.uz

Submission #1031907

# Submission time Handle Problem Language Result Execution time Memory
1031907 2024-07-23T08:37:52 Z 정민찬(#10962) Golf (JOI17_golf) C++17
10 / 100
 297 ms 108280 KB 
#include <bits/stdc++.h>

using namespace std;

int board[3010][3010];
int dist[3010][3010][4];
int vis[3010][3010][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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 158 ms 108280 KB Output is correct
6 Correct 89 ms 83236 KB Output is correct
7 Correct 167 ms 91912 KB Output is correct
8 Correct 146 ms 96296 KB Output is correct
9 Correct 156 ms 87024 KB Output is correct
10 Correct 68 ms 61372 KB Output is correct
11 Correct 67 ms 75168 KB Output is correct
12 Correct 43 ms 49164 KB Output is correct
13 Correct 137 ms 90136 KB Output is correct
14 Correct 140 ms 88624 KB Output is correct
15 Correct 63 ms 20568 KB Output is correct
16 Correct 297 ms 60444 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 158 ms 108280 KB Output is correct
6 Correct 89 ms 83236 KB Output is correct
7 Correct 167 ms 91912 KB Output is correct
8 Correct 146 ms 96296 KB Output is correct
9 Correct 156 ms 87024 KB Output is correct
10 Correct 68 ms 61372 KB Output is correct
11 Correct 67 ms 75168 KB Output is correct
12 Correct 43 ms 49164 KB Output is correct
13 Correct 137 ms 90136 KB Output is correct
14 Correct 140 ms 88624 KB Output is correct
15 Correct 63 ms 20568 KB Output is correct
16 Correct 297 ms 60444 KB Output is correct
17 Runtime error 26 ms 18000 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 158 ms 108280 KB Output is correct
6 Correct 89 ms 83236 KB Output is correct
7 Correct 167 ms 91912 KB Output is correct
8 Correct 146 ms 96296 KB Output is correct
9 Correct 156 ms 87024 KB Output is correct
10 Correct 68 ms 61372 KB Output is correct
11 Correct 67 ms 75168 KB Output is correct
12 Correct 43 ms 49164 KB Output is correct
13 Correct 137 ms 90136 KB Output is correct
14 Correct 140 ms 88624 KB Output is correct
15 Correct 63 ms 20568 KB Output is correct
16 Correct 297 ms 60444 KB Output is correct
17 Runtime error 26 ms 18000 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -