oj.uz

Submission #253270

# Submission time Handle Problem Language Result Execution time Memory
253270 2020-07-27T14:55:53 Z srvlt Golf (JOI17_golf) C++14
10 / 100
 148 ms 43692 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 1003;
int s, t, u, v, n, bad[n0][n0], l[2][n0], r[2][n0];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int d[4][n0][n0];

bool ok(int c, int x, int y) {
	return x >= 1 && x <= 1000 && y >= 1 && y <= 1000;
}

void bfs(int x, int y) {
	memset(& d, 0x3f, sizeof(d));
	deque <array <int, 3>> q;
	for (int i = 0; i < 4; i++) {
		q.push_front({i, x, y});
		d[i][x][y] = 0;
	}
	while (!q.empty()) {
		array <int, 3> v = q.front();
		int c = v[0], x = v[1], y = v[2];
		q.pop_front();
		int X = x + dx[c], Y = y + dy[c];
		if (ok(c, X, Y)) {
			int flag = 0;
			if (bad[x][y] > 0 && bad[x][y] == bad[X][Y]) {
				flag = 1;
				int ind = bad[x][y];
				if ((x == l[0][ind] && X == l[0][ind]) || (x == r[0][ind] && X == r[0][ind]))
					flag = 0;
				if ((y == l[1][ind] && Y == l[1][ind]) || (y == r[1][ind] && Y == r[1][ind]))
					flag = 0;
			}
			if (!flag && d[c][X][Y] > d[c][x][y]) {
				d[c][X][Y] = d[c][x][y];
				q.push_front({c, X, Y});
			}
		}
		for (int i = 0; i < 4; i++) {
			if (i != c && d[i][x][y] > d[c][x][y] + 1) {
				d[i][x][y] = d[c][x][y] + 1;
				q.push_back({i, x, y});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> s >> t >> u >> v >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[0][i] >> r[0][i] >> l[1][i] >> r[1][i];
		for (int j = l[0][i]; j <= r[0][i]; j++)
			for (int k = l[1][i]; k <= r[1][i]; k++)
				bad[j][k] = i;
	}
	bfs(s, t);
	int res = (int)1e9;
	for (int i = 0; i < 4; i++)
		res = min(res, d[i][u][v]);
	cout << res + 1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 43692 KB Output is correct
2 Correct 126 ms 34472 KB Output is correct
3 Correct 92 ms 37932 KB Output is correct
4 Correct 44 ms 24704 KB Output is correct
5 Correct 48 ms 23800 KB Output is correct
6 Correct 45 ms 22904 KB Output is correct
7 Correct 45 ms 22584 KB Output is correct
8 Correct 47 ms 22656 KB Output is correct
9 Correct 41 ms 22272 KB Output is correct
10 Correct 45 ms 22648 KB Output is correct
11 Correct 48 ms 23160 KB Output is correct
12 Correct 52 ms 22008 KB Output is correct
13 Correct 39 ms 22136 KB Output is correct
14 Correct 55 ms 23032 KB Output is correct
15 Correct 148 ms 32604 KB Output is correct
16 Correct 145 ms 21496 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 43692 KB Output is correct
2 Correct 126 ms 34472 KB Output is correct
3 Correct 92 ms 37932 KB Output is correct
4 Correct 44 ms 24704 KB Output is correct
5 Correct 48 ms 23800 KB Output is correct
6 Correct 45 ms 22904 KB Output is correct
7 Correct 45 ms 22584 KB Output is correct
8 Correct 47 ms 22656 KB Output is correct
9 Correct 41 ms 22272 KB Output is correct
10 Correct 45 ms 22648 KB Output is correct
11 Correct 48 ms 23160 KB Output is correct
12 Correct 52 ms 22008 KB Output is correct
13 Correct 39 ms 22136 KB Output is correct
14 Correct 55 ms 23032 KB Output is correct
15 Correct 148 ms 32604 KB Output is correct
16 Correct 145 ms 21496 KB Output is correct
17 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 43692 KB Output is correct
2 Correct 126 ms 34472 KB Output is correct
3 Correct 92 ms 37932 KB Output is correct
4 Correct 44 ms 24704 KB Output is correct
5 Correct 48 ms 23800 KB Output is correct
6 Correct 45 ms 22904 KB Output is correct
7 Correct 45 ms 22584 KB Output is correct
8 Correct 47 ms 22656 KB Output is correct
9 Correct 41 ms 22272 KB Output is correct
10 Correct 45 ms 22648 KB Output is correct
11 Correct 48 ms 23160 KB Output is correct
12 Correct 52 ms 22008 KB Output is correct
13 Correct 39 ms 22136 KB Output is correct
14 Correct 55 ms 23032 KB Output is correct
15 Correct 148 ms 32604 KB Output is correct
16 Correct 145 ms 21496 KB Output is correct
17 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -