oj.uz

Submission #253297

# Submission time Handle Problem Language Result Execution time Memory
253297 2020-07-27T16:13:18 Z srvlt Golf (JOI17_golf) C++14
30 / 100
 879 ms 231272 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 = 2123;
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 <= 2100 && y >= 1 && y <= 2100;
}
 
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});
			}
		}
	}
}
 
vector <int> vx, vy;
 
void cx(int & x) {
	x = lower_bound(all(vx), x) - vx.begin() + 1;
}
 
void cy(int & y) {
	y = lower_bound(all(vy), y) - vy.begin() + 1;
}
 
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;
	vx.pb(s), vx.pb(u);
	vy.pb(t), vy.pb(v);
	for (int i = 1; i <= n; i++) {
		cin >> l[0][i] >> r[0][i] >> l[1][i] >> r[1][i];
		vx.pb(l[0][i]), vx.pb(r[0][i]);
		vy.pb(l[1][i]), vy.pb(r[1][i]);
	}
	sort(all(vx));
	vx.erase(unique(all(vx)), vx.end());
	sort(all(vy));
	vy.erase(unique(all(vy)), vy.end());
	cx(s), cy(t), cx(u), cy(v);
	for (int i = 1; i <= n; i++) {
		cx(l[0][i]), cy(l[1][i]);
		cx(r[0][i]), cy(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 <= 2105);
	cout << res + 1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 231024 KB Output is correct
2 Correct 879 ms 231272 KB Output is correct
3 Correct 870 ms 229864 KB Output is correct
4 Correct 841 ms 230856 KB Output is correct
5 Correct 661 ms 209644 KB Output is correct
6 Correct 412 ms 179612 KB Output is correct
7 Correct 455 ms 214380 KB Output is correct
8 Correct 395 ms 207340 KB Output is correct
9 Correct 489 ms 214372 KB Output is correct
10 Correct 552 ms 212736 KB Output is correct
11 Correct 669 ms 213352 KB Output is correct
12 Correct 548 ms 213616 KB Output is correct
13 Correct 667 ms 214376 KB Output is correct
14 Correct 451 ms 179100 KB Output is correct
15 Correct 862 ms 227560 KB Output is correct
16 Correct 781 ms 213772 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 231024 KB Output is correct
2 Correct 879 ms 231272 KB Output is correct
3 Correct 870 ms 229864 KB Output is correct
4 Correct 841 ms 230856 KB Output is correct
5 Correct 661 ms 209644 KB Output is correct
6 Correct 412 ms 179612 KB Output is correct
7 Correct 455 ms 214380 KB Output is correct
8 Correct 395 ms 207340 KB Output is correct
9 Correct 489 ms 214372 KB Output is correct
10 Correct 552 ms 212736 KB Output is correct
11 Correct 669 ms 213352 KB Output is correct
12 Correct 548 ms 213616 KB Output is correct
13 Correct 667 ms 214376 KB Output is correct
14 Correct 451 ms 179100 KB Output is correct
15 Correct 862 ms 227560 KB Output is correct
16 Correct 781 ms 213772 KB Output is correct
17 Correct 325 ms 121020 KB Output is correct
18 Correct 370 ms 118392 KB Output is correct
19 Correct 287 ms 114800 KB Output is correct
20 Correct 315 ms 115444 KB Output is correct
21 Correct 324 ms 103596 KB Output is correct
22 Correct 298 ms 114976 KB Output is correct
23 Correct 299 ms 111508 KB Output is correct
24 Correct 283 ms 110616 KB Output is correct
25 Correct 294 ms 108064 KB Output is correct
26 Correct 311 ms 111832 KB Output is correct
27 Correct 836 ms 225636 KB Output is correct
28 Correct 767 ms 209636 KB Output is correct
29 Correct 774 ms 209000 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 231024 KB Output is correct
2 Correct 879 ms 231272 KB Output is correct
3 Correct 870 ms 229864 KB Output is correct
4 Correct 841 ms 230856 KB Output is correct
5 Correct 661 ms 209644 KB Output is correct
6 Correct 412 ms 179612 KB Output is correct
7 Correct 455 ms 214380 KB Output is correct
8 Correct 395 ms 207340 KB Output is correct
9 Correct 489 ms 214372 KB Output is correct
10 Correct 552 ms 212736 KB Output is correct
11 Correct 669 ms 213352 KB Output is correct
12 Correct 548 ms 213616 KB Output is correct
13 Correct 667 ms 214376 KB Output is correct
14 Correct 451 ms 179100 KB Output is correct
15 Correct 862 ms 227560 KB Output is correct
16 Correct 781 ms 213772 KB Output is correct
17 Correct 325 ms 121020 KB Output is correct
18 Correct 370 ms 118392 KB Output is correct
19 Correct 287 ms 114800 KB Output is correct
20 Correct 315 ms 115444 KB Output is correct
21 Correct 324 ms 103596 KB Output is correct
22 Correct 298 ms 114976 KB Output is correct
23 Correct 299 ms 111508 KB Output is correct
24 Correct 283 ms 110616 KB Output is correct
25 Correct 294 ms 108064 KB Output is correct
26 Correct 311 ms 111832 KB Output is correct
27 Correct 836 ms 225636 KB Output is correct
28 Correct 767 ms 209636 KB Output is correct
29 Correct 774 ms 209000 KB Output is correct
30 Runtime error 220 ms 148236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -