제출 #122119

#제출 시각아이디문제언어결과실행 시간메모리
122119egorlifarGolf (JOI17_golf)C++17
30 / 100
2386 ms452924 KiB
/* ЗАПУСКАЕМ ░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░ ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░ */ #include <iostream> #include <complex> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <numeric> #include <cstring> #include <ctime> #include <cstdlib> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <list> #include <cmath> #include <bitset> #include <cassert> #include <queue> #include <stack> #include <deque> #include <random> #include <chrono> using namespace std; template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) { if (x > y) { x = y; return 1; } else { return 0; } } template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) { if (x < y) { x = y; return 1; } else { return 0; } } #define all(c) (c).begin(), (c).end() #define sz(c) (int)(c).size() #define mp make_pair #define pb push_back #define read(FILENAME) freopen((string(FILENAME) + ".in").c_str(), "r", stdin) #define write(FILENAME) freopen((string(FILENAME) + ".out").c_str(), "w", stdout); void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int N, sx, sy, gx, gy, px[1009], qx[1009], py[1009], qy[1009], r[4099][4099], dist[4099][4099][5]; vector<int>X, Y; queue<tuple<int, int, int> > Q[10000]; int solve() { for (int i = 0; i <= sz(X) * 2; i++) { for (int j = 0; j <= sz(Y) * 2; j++) { for (int k = 0; k < 5; k++) { dist[i][j][k] = (1 << 30); } } } int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 }; dist[sx][sy][4] = 0; Q[0].push(make_tuple(sx, sy, 4)); for (int i = 0; i < 8000; i++) { while (!Q[i].empty()) { int cx = get<0>(Q[i].front()), cy = get<1>(Q[i].front()), dir = get<2>(Q[i].front()); Q[i].pop(); if (dir != 4 && dist[cx][cy][4] > dist[cx][cy][dir]) { dist[cx][cy][4] = dist[cx][cy][dir]; Q[dist[cx][cy][4]].push(make_tuple(cx, cy, 4)); } int ex = cx + dx[dir], ey = cy + dy[dir]; if (ex >= 0 && ey >= 0 && ex <= sz(X) * 2 && ey <= sz(Y) * 2 && r[ex][ey] == 0 && dist[ex][ey][dir] > dist[cx][cy][dir]) { dist[ex][ey][dir] = dist[cx][cy][dir]; Q[dist[ex][ey][dir]].push(make_tuple(ex, ey, dir)); } if (dir == 4) { for (int j = 0; j < 4; j++) { if (dist[cx][cy][j] > dist[cx][cy][dir] + 1) { dist[cx][cy][j] = dist[cx][cy][dir] + 1; Q[dist[cx][cy][j]].push(make_tuple(cx, cy, j)); } } } } } return dist[gx][gy][4]; } int main() { fast_io(); // read("input"); cin >> sx >> sy >> gx >> gy >> N; X.push_back(sx); X.push_back(gx); Y.push_back(sy); Y.push_back(gy); for (int i = 1; i <= N; i++) { cin >> px[i] >> qx[i] >> py[i] >> qy[i]; X.push_back(px[i]); X.push_back(qx[i]); Y.push_back(py[i]); Y.push_back(qy[i]); } sort(all(X)); X.erase(unique(all(X)), X.end()); sort(all(Y)); Y.erase(unique(all(Y)), Y.end()); for (int i = 1; i <= N; i++) { px[i] = lower_bound(all(X), px[i]) - X.begin(); qx[i] = lower_bound(all(X), qx[i]) - X.begin(); py[i] = lower_bound(all(Y), py[i]) - Y.begin(); qy[i] = lower_bound(all(Y), qy[i]) - Y.begin(); r[px[i] * 2 + 1][py[i] * 2 + 1]++; r[px[i] * 2 + 1][qy[i] * 2]--; r[qx[i] * 2][py[i] * 2 + 1]--; r[qx[i] * 2][qy[i] * 2]++; } sx = lower_bound(all(X), sx) - X.begin(); sx *= 2; sy = lower_bound(all(Y), sy) - Y.begin(); sy *= 2; gx = lower_bound(all(X), gx) - X.begin(); gx *= 2; gy = lower_bound(all(Y), gy) - Y.begin(); gy *= 2; for (int i = 0; i <= sz(X) * 2; i++) { for (int j = 1; j <= sz(Y) * 2; j++) { r[i][j] += r[i][j - 1]; } } for (int i = 0; i <= sz(Y) * 2; i++) { for (int j = 1; j <= sz(X) * 2; j++) { r[j][i] += r[j - 1][i]; } } cout << solve() << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...