oj.uz

Submission #253293

# Submission time Handle Problem Language Result Execution time Memory
253293 2020-07-27T15:59:48 Z srvlt Golf (JOI17_golf) C++14
10 / 100
 214 ms 107260 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 <= 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});
			}
		}
	}
}
 
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 107 ms 107260 KB Output is correct
2 Correct 214 ms 107256 KB Output is correct
3 Correct 213 ms 106620 KB Output is correct
4 Correct 203 ms 107136 KB Output is correct
5 Correct 118 ms 90420 KB Output is correct
6 Correct 106 ms 85256 KB Output is correct
7 Correct 127 ms 91988 KB Output is correct
8 Correct 106 ms 89132 KB Output is correct
9 Correct 116 ms 90412 KB Output is correct
10 Correct 135 ms 90672 KB Output is correct
11 Correct 119 ms 89480 KB Output is correct
12 Correct 135 ms 90924 KB Output is correct
13 Correct 113 ms 90412 KB Output is correct
14 Correct 114 ms 85764 KB Output is correct
15 Correct 193 ms 103676 KB Output is correct
16 Correct 190 ms 89992 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 107260 KB Output is correct
2 Correct 214 ms 107256 KB Output is correct
3 Correct 213 ms 106620 KB Output is correct
4 Correct 203 ms 107136 KB Output is correct
5 Correct 118 ms 90420 KB Output is correct
6 Correct 106 ms 85256 KB Output is correct
7 Correct 127 ms 91988 KB Output is correct
8 Correct 106 ms 89132 KB Output is correct
9 Correct 116 ms 90412 KB Output is correct
10 Correct 135 ms 90672 KB Output is correct
11 Correct 119 ms 89480 KB Output is correct
12 Correct 135 ms 90924 KB Output is correct
13 Correct 113 ms 90412 KB Output is correct
14 Correct 114 ms 85764 KB Output is correct
15 Correct 193 ms 103676 KB Output is correct
16 Correct 190 ms 89992 KB Output is correct
17 Incorrect 47 ms 87288 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 107260 KB Output is correct
2 Correct 214 ms 107256 KB Output is correct
3 Correct 213 ms 106620 KB Output is correct
4 Correct 203 ms 107136 KB Output is correct
5 Correct 118 ms 90420 KB Output is correct
6 Correct 106 ms 85256 KB Output is correct
7 Correct 127 ms 91988 KB Output is correct
8 Correct 106 ms 89132 KB Output is correct
9 Correct 116 ms 90412 KB Output is correct
10 Correct 135 ms 90672 KB Output is correct
11 Correct 119 ms 89480 KB Output is correct
12 Correct 135 ms 90924 KB Output is correct
13 Correct 113 ms 90412 KB Output is correct
14 Correct 114 ms 85764 KB Output is correct
15 Correct 193 ms 103676 KB Output is correct
16 Correct 190 ms 89992 KB Output is correct
17 Incorrect 47 ms 87288 KB Output isn't correct
18 Halted 0 ms 0 KB -