oj.uz

Submission #253280

# Submission time Handle Problem Language Result Execution time Memory
253280 2020-07-27T15:38:41 Z srvlt Golf (JOI17_golf) C++14
0 / 100
 173 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]);
	assert(res + 1 <= 100);
	cout << res + 1;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 43692 KB Output is correct
2 Correct 125 ms 34476 KB Output is correct
3 Correct 99 ms 37932 KB Output is correct
4 Correct 51 ms 24704 KB Output is correct
5 Correct 51 ms 23800 KB Output is correct
6 Correct 48 ms 22912 KB Output is correct
7 Correct 56 ms 22456 KB Output is correct
8 Correct 53 ms 22648 KB Output is correct
9 Correct 47 ms 22272 KB Output is correct
10 Correct 47 ms 22776 KB Output is correct
11 Correct 50 ms 23032 KB Output is correct
12 Correct 44 ms 22008 KB Output is correct
13 Correct 41 ms 22140 KB Output is correct
14 Correct 47 ms 23040 KB Output is correct
15 Runtime error 173 ms 39096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 43692 KB Output is correct
2 Correct 125 ms 34476 KB Output is correct
3 Correct 99 ms 37932 KB Output is correct
4 Correct 51 ms 24704 KB Output is correct
5 Correct 51 ms 23800 KB Output is correct
6 Correct 48 ms 22912 KB Output is correct
7 Correct 56 ms 22456 KB Output is correct
8 Correct 53 ms 22648 KB Output is correct
9 Correct 47 ms 22272 KB Output is correct
10 Correct 47 ms 22776 KB Output is correct
11 Correct 50 ms 23032 KB Output is correct
12 Correct 44 ms 22008 KB Output is correct
13 Correct 41 ms 22140 KB Output is correct
14 Correct 47 ms 23040 KB Output is correct
15 Runtime error 173 ms 39096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 43692 KB Output is correct
2 Correct 125 ms 34476 KB Output is correct
3 Correct 99 ms 37932 KB Output is correct
4 Correct 51 ms 24704 KB Output is correct
5 Correct 51 ms 23800 KB Output is correct
6 Correct 48 ms 22912 KB Output is correct
7 Correct 56 ms 22456 KB Output is correct
8 Correct 53 ms 22648 KB Output is correct
9 Correct 47 ms 22272 KB Output is correct
10 Correct 47 ms 22776 KB Output is correct
11 Correct 50 ms 23032 KB Output is correct
12 Correct 44 ms 22008 KB Output is correct
13 Correct 41 ms 22140 KB Output is correct
14 Correct 47 ms 23040 KB Output is correct
15 Runtime error 173 ms 39096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -