oj.uz

Submission #590642

# Submission time Handle Problem Language Result Execution time Memory
590642 2022-07-06T07:58:24 Z 이동현(#8415) Golf (JOI17_golf) C++17
0 / 100
 315 ms 87280 KB 
#include <bits/stdc++.h>

using namespace std;

int wayx[2004][2004], wayy[2004][2004];
int wx[4] = {-1, 0, 1, 0}, wy[4] = {0, 1, 0, -1};
int que[2004 * 2004][2];
int dist[2004][2004];
int f, r;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey;
    int n; cin >> n;
    vector<vector<int>> a(n, vector<int>(4));
    vector<int> xsrt, ysrt;
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        xsrt.push_back(a[i][0]), xsrt.push_back(a[i][1]);
        ysrt.push_back(a[i][2]), ysrt.push_back(a[i][3]);
    }
    xsrt.push_back(sx), xsrt.push_back(ex);
    ysrt.push_back(sy), ysrt.push_back(ey);
    xsrt.push_back(0), ysrt.push_back(0);
    sort(xsrt.begin(), xsrt.end()), xsrt.erase(unique(xsrt.begin(), xsrt.end()), xsrt.end());
    sort(ysrt.begin(), ysrt.end()), ysrt.erase(unique(ysrt.begin(), ysrt.end()), ysrt.end());
    auto getx = [&](int x){return lower_bound(xsrt.begin(), xsrt.end(), x) - xsrt.begin();};
    auto gety = [&](int y){return lower_bound(ysrt.begin(), ysrt.end(), y) - ysrt.begin();};
    sx = getx(sx), ex = getx(ex), sy = gety(sy), ey = gety(ey);
    //cout << sx << ' ' << sy << ' ' << ex << ' ' << ey << endl;
    for(int i = 0; i < n; ++i){
        a[i][0] = getx(a[i][0]), a[i][1] = getx(a[i][1]);
        a[i][2] = gety(a[i][2]), a[i][3] = gety(a[i][3]);
        //cout << a[i][0] << ' ' << a[i][1] << ' ' << a[i][2] << ' ' << a[i][3] << endl;
    }
    for(int i = 0; i < n; ++i){
        for(int j = a[i][0] + 1; j < a[i][1]; ++j){
            wayx[j][a[i][2] + 1] = wayx[j][a[i][3]] = 1;
        }
        for(int j = a[i][2] + 1; j < a[i][3]; ++j){
            wayy[a[i][0] + 1][j] = wayy[a[i][1]][j] = 1;
        }
    }
    vector<set<int>> xset((int)xsrt.size()), yset((int)ysrt.size());
    for(int i = 0; i < (int)xsrt.size(); ++i){
        for(int j = 0; j < (int)ysrt.size(); ++j){
            xset[i].insert(j);
            if(j) wayx[i][j] += wayx[i][j - 1];
        }
    }
    for(int j = 0; j < (int)ysrt.size(); ++j){
        for(int i = 0; i < (int)xsrt.size(); ++i){
            yset[j].insert(i);
            if(i) wayy[i][j] += wayy[i - 1][j];
        }
    }
    auto cantx = [&](int x, int y1, int y2)->int{
        if(y1 > y2) swap(y1, y2);
        int val = wayx[x][y2];
        if(y1) val -= wayx[x][y1 - 1];
        return val;
    };
    auto canty = [&](int y, int x1, int x2)->int{
        if(x1 > x2) swap(x1, x2);
        int val = wayy[x2][y];
        if(x1) val -= wayy[x1 - 1][y];
        return val;
    };
    que[r][0] = sx, que[r++][1] = sy, dist[sx][sy] = 1;
    while(f < r){
        int x = que[f][0], y = que[f][1];
        int far = dist[x][y];
        if(x == ex && y == ey){
            cout << far - 1 << '\n';
            return 0;
        }
        auto p = xset[x].lower_bound(y);
        while(p != xset[x].end()){
            if(cantx(x, y, *p)){
                break;
            }
            if(!dist[x][*p]){
                dist[x][*p] = far + 1;
                que[r][0] = x, que[r++][1] = *p;
            }
            xset[x].erase(p++);
        }
        while(true){
            p = xset[x].lower_bound(y);
            if(p == xset[x].begin()) break;
            --p;
            if(cantx(x, y, *p)){
                break;
            }
            if(!dist[x][*p]){
                dist[x][*p] = far + 1;
                que[r][0] = x, que[r++][1] = *p;
            }
            xset[x].erase(p++);
        }
        p = yset[y].lower_bound(x);
        while(p != yset[y].end()){
            if(canty(y, x, *p)){
                break;
            }
            if(!dist[*p][y]){
                dist[*p][y] = far + 1;
                que[r][0] = *p, que[r++][1] = y;
            }
            yset[y].erase(p++);
        }
        while(true){
            p = yset[y].lower_bound(x);
            if(p == yset[y].begin()) break;
            --p;
            if(canty(y, x, *p)){
                break;
            }
            if(!dist[*p][y]){
                dist[*p][y] = far + 1;
                que[r][0] = *p, que[r++][1] = y;
            }
            yset[y].erase(p++);
        }
        ++f;
    }
    assert(0);
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 11 ms 6080 KB Output is correct
5 Correct 270 ms 77896 KB Output is correct
6 Correct 281 ms 81672 KB Output is correct
7 Correct 269 ms 75684 KB Output is correct
8 Correct 315 ms 84812 KB Output is correct
9 Correct 295 ms 79692 KB Output is correct
10 Correct 244 ms 82164 KB Output is correct
11 Incorrect 285 ms 87280 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 11 ms 6080 KB Output is correct
5 Correct 270 ms 77896 KB Output is correct
6 Correct 281 ms 81672 KB Output is correct
7 Correct 269 ms 75684 KB Output is correct
8 Correct 315 ms 84812 KB Output is correct
9 Correct 295 ms 79692 KB Output is correct
10 Correct 244 ms 82164 KB Output is correct
11 Incorrect 285 ms 87280 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 11 ms 6080 KB Output is correct
5 Correct 270 ms 77896 KB Output is correct
6 Correct 281 ms 81672 KB Output is correct
7 Correct 269 ms 75684 KB Output is correct
8 Correct 315 ms 84812 KB Output is correct
9 Correct 295 ms 79692 KB Output is correct
10 Correct 244 ms 82164 KB Output is correct
11 Incorrect 285 ms 87280 KB Output isn't correct
12 Halted 0 ms 0 KB -