Submission #253297

#	Time	Username	Problem	Language	Result	Execution time	Memory
253297		srvlt	Golf (JOI17_golf)	C++14	30 / 100	879 ms	231272 KiB

golf

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70