제출 #122119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122119		egorlifar	Golf (JOI17_golf)	C++17	30 / 100	2386 ms	452924 KiB

golf

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#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;

}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70