oj.uz

Submission #122119

# Submission time Handle Problem Language Result Execution time Memory
122119 2019-06-27T14:58:44 Z egorlifar Golf (JOI17_golf) C++17
30 / 100
 2386 ms 452924 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7040 KB Output is correct
2 Correct 10 ms 7168 KB Output is correct
3 Correct 12 ms 7296 KB Output is correct
4 Correct 30 ms 13952 KB Output is correct
5 Correct 269 ms 89336 KB Output is correct
6 Correct 244 ms 89596 KB Output is correct
7 Correct 303 ms 84216 KB Output is correct
8 Correct 249 ms 91388 KB Output is correct
9 Correct 322 ms 85624 KB Output is correct
10 Correct 278 ms 90716 KB Output is correct
11 Correct 294 ms 95612 KB Output is correct
12 Correct 254 ms 87288 KB Output is correct
13 Correct 241 ms 89336 KB Output is correct
14 Correct 314 ms 92152 KB Output is correct
15 Correct 95 ms 29432 KB Output is correct
16 Correct 394 ms 83048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7040 KB Output is correct
2 Correct 10 ms 7168 KB Output is correct
3 Correct 12 ms 7296 KB Output is correct
4 Correct 30 ms 13952 KB Output is correct
5 Correct 269 ms 89336 KB Output is correct
6 Correct 244 ms 89596 KB Output is correct
7 Correct 303 ms 84216 KB Output is correct
8 Correct 249 ms 91388 KB Output is correct
9 Correct 322 ms 85624 KB Output is correct
10 Correct 278 ms 90716 KB Output is correct
11 Correct 294 ms 95612 KB Output is correct
12 Correct 254 ms 87288 KB Output is correct
13 Correct 241 ms 89336 KB Output is correct
14 Correct 314 ms 92152 KB Output is correct
15 Correct 95 ms 29432 KB Output is correct
16 Correct 394 ms 83048 KB Output is correct
17 Correct 1949 ms 443184 KB Output is correct
18 Correct 2068 ms 444320 KB Output is correct
19 Correct 1711 ms 432260 KB Output is correct
20 Correct 1819 ms 439396 KB Output is correct
21 Correct 2121 ms 452924 KB Output is correct
22 Correct 1958 ms 448800 KB Output is correct
23 Correct 1948 ms 436468 KB Output is correct
24 Correct 1726 ms 435372 KB Output is correct
25 Correct 2386 ms 449012 KB Output is correct
26 Correct 2331 ms 426248 KB Output is correct
27 Correct 145 ms 37624 KB Output is correct
28 Correct 489 ms 97248 KB Output is correct
29 Correct 493 ms 99660 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7040 KB Output is correct
2 Correct 10 ms 7168 KB Output is correct
3 Correct 12 ms 7296 KB Output is correct
4 Correct 30 ms 13952 KB Output is correct
5 Correct 269 ms 89336 KB Output is correct
6 Correct 244 ms 89596 KB Output is correct
7 Correct 303 ms 84216 KB Output is correct
8 Correct 249 ms 91388 KB Output is correct
9 Correct 322 ms 85624 KB Output is correct
10 Correct 278 ms 90716 KB Output is correct
11 Correct 294 ms 95612 KB Output is correct
12 Correct 254 ms 87288 KB Output is correct
13 Correct 241 ms 89336 KB Output is correct
14 Correct 314 ms 92152 KB Output is correct
15 Correct 95 ms 29432 KB Output is correct
16 Correct 394 ms 83048 KB Output is correct
17 Correct 1949 ms 443184 KB Output is correct
18 Correct 2068 ms 444320 KB Output is correct
19 Correct 1711 ms 432260 KB Output is correct
20 Correct 1819 ms 439396 KB Output is correct
21 Correct 2121 ms 452924 KB Output is correct
22 Correct 1958 ms 448800 KB Output is correct
23 Correct 1948 ms 436468 KB Output is correct
24 Correct 1726 ms 435372 KB Output is correct
25 Correct 2386 ms 449012 KB Output is correct
26 Correct 2331 ms 426248 KB Output is correct
27 Correct 145 ms 37624 KB Output is correct
28 Correct 489 ms 97248 KB Output is correct
29 Correct 493 ms 99660 KB Output is correct
30 Runtime error 34 ms 14200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -