| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 253272 |
2020-07-27T15:04:12 Z |
srvlt |
Golf (JOI17_golf) |
C++14 |
|
161 ms |
95148 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]);
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;
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
95148 KB |
Output is correct |
| 2 |
Correct |
161 ms |
92844 KB |
Output is correct |
| 3 |
Correct |
134 ms |
92208 KB |
Output is correct |
| 4 |
Incorrect |
38 ms |
78712 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
95148 KB |
Output is correct |
| 2 |
Correct |
161 ms |
92844 KB |
Output is correct |
| 3 |
Correct |
134 ms |
92208 KB |
Output is correct |
| 4 |
Incorrect |
38 ms |
78712 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
95148 KB |
Output is correct |
| 2 |
Correct |
161 ms |
92844 KB |
Output is correct |
| 3 |
Correct |
134 ms |
92208 KB |
Output is correct |
| 4 |
Incorrect |
38 ms |
78712 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
