oj.uz

Submission #253294

# Submission time Handle Problem Language Result Execution time Memory
253294 2020-07-27T16:00:30 Z srvlt Golf (JOI17_golf) C++14
30 / 100
 881 ms 231268 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]);
	cout << res + 1;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 231132 KB Output is correct
2 Correct 881 ms 231268 KB Output is correct
3 Correct 879 ms 229992 KB Output is correct
4 Correct 841 ms 230868 KB Output is correct
5 Correct 648 ms 209516 KB Output is correct
6 Correct 421 ms 179484 KB Output is correct
7 Correct 476 ms 214384 KB Output is correct
8 Correct 390 ms 207412 KB Output is correct
9 Correct 493 ms 214504 KB Output is correct
10 Correct 536 ms 212820 KB Output is correct
11 Correct 666 ms 213348 KB Output is correct
12 Correct 552 ms 213612 KB Output is correct
13 Correct 692 ms 214120 KB Output is correct
14 Correct 453 ms 179104 KB Output is correct
15 Correct 845 ms 227688 KB Output is correct
16 Correct 775 ms 213864 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 231132 KB Output is correct
2 Correct 881 ms 231268 KB Output is correct
3 Correct 879 ms 229992 KB Output is correct
4 Correct 841 ms 230868 KB Output is correct
5 Correct 648 ms 209516 KB Output is correct
6 Correct 421 ms 179484 KB Output is correct
7 Correct 476 ms 214384 KB Output is correct
8 Correct 390 ms 207412 KB Output is correct
9 Correct 493 ms 214504 KB Output is correct
10 Correct 536 ms 212820 KB Output is correct
11 Correct 666 ms 213348 KB Output is correct
12 Correct 552 ms 213612 KB Output is correct
13 Correct 692 ms 214120 KB Output is correct
14 Correct 453 ms 179104 KB Output is correct
15 Correct 845 ms 227688 KB Output is correct
16 Correct 775 ms 213864 KB Output is correct
17 Correct 332 ms 121060 KB Output is correct
18 Correct 357 ms 118344 KB Output is correct
19 Correct 278 ms 115056 KB Output is correct
20 Correct 308 ms 115448 KB Output is correct
21 Correct 300 ms 103596 KB Output is correct
22 Correct 295 ms 114976 KB Output is correct
23 Correct 288 ms 111504 KB Output is correct
24 Correct 274 ms 110888 KB Output is correct
25 Correct 290 ms 108064 KB Output is correct
26 Correct 316 ms 111708 KB Output is correct
27 Correct 842 ms 225700 KB Output is correct
28 Correct 760 ms 209640 KB Output is correct
29 Correct 757 ms 209272 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 231132 KB Output is correct
2 Correct 881 ms 231268 KB Output is correct
3 Correct 879 ms 229992 KB Output is correct
4 Correct 841 ms 230868 KB Output is correct
5 Correct 648 ms 209516 KB Output is correct
6 Correct 421 ms 179484 KB Output is correct
7 Correct 476 ms 214384 KB Output is correct
8 Correct 390 ms 207412 KB Output is correct
9 Correct 493 ms 214504 KB Output is correct
10 Correct 536 ms 212820 KB Output is correct
11 Correct 666 ms 213348 KB Output is correct
12 Correct 552 ms 213612 KB Output is correct
13 Correct 692 ms 214120 KB Output is correct
14 Correct 453 ms 179104 KB Output is correct
15 Correct 845 ms 227688 KB Output is correct
16 Correct 775 ms 213864 KB Output is correct
17 Correct 332 ms 121060 KB Output is correct
18 Correct 357 ms 118344 KB Output is correct
19 Correct 278 ms 115056 KB Output is correct
20 Correct 308 ms 115448 KB Output is correct
21 Correct 300 ms 103596 KB Output is correct
22 Correct 295 ms 114976 KB Output is correct
23 Correct 288 ms 111504 KB Output is correct
24 Correct 274 ms 110888 KB Output is correct
25 Correct 290 ms 108064 KB Output is correct
26 Correct 316 ms 111708 KB Output is correct
27 Correct 842 ms 225700 KB Output is correct
28 Correct 760 ms 209640 KB Output is correct
29 Correct 757 ms 209272 KB Output is correct
30 Runtime error 220 ms 151700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -