oj.uz

Submission #93234

# Submission time Handle Problem Language Result Execution time Memory
93234 2019-01-07T10:25:27 Z Alexa2001 Golf (JOI17_golf) C++17
30 / 100
 1502 ms 79564 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2010;

map<int,int> mpx, mpy;
int X1, X2, Y1, Y2, n, N, M;

int dist[Nmax][Nmax][4];
int a[Nmax], b[Nmax], c[Nmax], d[Nmax], mat[Nmax][Nmax];
int i, j;
bool blocked[Nmax][Nmax][4];

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

struct state
{
    int x, y, dir;
};

int solve()
{
    queue<state> q;

    q.push({X1, Y1, 0});
    q.push({X1, Y1, 1});
    q.push({X1, Y1, 2});
    q.push({X1, Y1, 3});

    int x, y, dir, i, X, Y, Dist;

    for(x=1; x<=N; ++x)
        for(y=1; y<=M; ++y)
            for(dir=0; dir<4; ++dir)
                dist[x][y][dir] = ((x==X1 && y==Y1) ? 0 : 10 * Nmax);

    while(q.size())
    {
        x = q.front().x;
        y = q.front().y;
        dir = q.front().dir;
        q.pop();

        for(i=0; i<4; ++i)
        {
            X = x + dx[i];
            Y = y + dy[i];
            Dist = dist[x][y][dir] + (i != dir);

            if(dist[X][Y][i] > Dist && !blocked[X][Y][i])
            {
                dist[X][Y][i] = Dist;
                q.push({X, Y, i});
            }
        }
    }

    int ans = 10 * Nmax;
    for(i=0; i<4; ++i)
        ans = min(ans, dist[X2][Y2][i]);
    return ans;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> X1 >> Y1 >> X2 >> Y2;
    cin >> n;
    mpx[X1] = mpx[X2] = mpy[Y1] = mpy[Y2] = 1;

    int i;
    for(i=1; i<=n; ++i)
    {
        cin >> a[i] >> c[i] >> b[i] >> d[i];
        mpx[a[i]] = mpx[c[i]] = mpy[b[i]] = mpy[d[i]] = 1;
    }

    for(auto &it : mpx) it.second = ++N;
    for(auto &it : mpy) it.second = ++M;

    X1 = mpx[X1]; X2 = mpx[X2];
    Y1 = mpy[Y1]; Y2 = mpy[Y2];

    for(i=1; i<=n; ++i)
    {
        a[i] = mpx[a[i]];
        b[i] = mpy[b[i]];
        c[i] = mpx[c[i]];
        d[i] = mpy[d[i]];
    }

    for(i=1; i<=n; ++i)
    {
        for(j=a[i]+1; j<=c[i]-1; ++j) blocked[j][b[i]+1][1] = blocked[j][d[i]-1][0] = 1;
        for(j=b[i]+1; j<=d[i]-1; ++j) blocked[a[i]+1][j][3] = blocked[c[i]-1][j][2] = 1;
    }

    cout << solve() + 1 << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 222 ms 18688 KB Output is correct
6 Correct 158 ms 19960 KB Output is correct
7 Correct 143 ms 18912 KB Output is correct
8 Correct 135 ms 20600 KB Output is correct
9 Correct 193 ms 19200 KB Output is correct
10 Correct 152 ms 20344 KB Output is correct
11 Correct 189 ms 21120 KB Output is correct
12 Correct 136 ms 19968 KB Output is correct
13 Correct 138 ms 20088 KB Output is correct
14 Correct 191 ms 20528 KB Output is correct
15 Correct 30 ms 6784 KB Output is correct
16 Correct 194 ms 19612 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 222 ms 18688 KB Output is correct
6 Correct 158 ms 19960 KB Output is correct
7 Correct 143 ms 18912 KB Output is correct
8 Correct 135 ms 20600 KB Output is correct
9 Correct 193 ms 19200 KB Output is correct
10 Correct 152 ms 20344 KB Output is correct
11 Correct 189 ms 21120 KB Output is correct
12 Correct 136 ms 19968 KB Output is correct
13 Correct 138 ms 20088 KB Output is correct
14 Correct 191 ms 20528 KB Output is correct
15 Correct 30 ms 6784 KB Output is correct
16 Correct 194 ms 19612 KB Output is correct
17 Correct 1265 ms 78084 KB Output is correct
18 Correct 744 ms 77876 KB Output is correct
19 Correct 740 ms 78644 KB Output is correct
20 Correct 1053 ms 78728 KB Output is correct
21 Correct 1502 ms 79564 KB Output is correct
22 Correct 1129 ms 79548 KB Output is correct
23 Correct 1064 ms 79296 KB Output is correct
24 Correct 1129 ms 79384 KB Output is correct
25 Correct 879 ms 79452 KB Output is correct
26 Correct 989 ms 79356 KB Output is correct
27 Correct 43 ms 8832 KB Output is correct
28 Correct 187 ms 22904 KB Output is correct
29 Correct 166 ms 23416 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 12 ms 2432 KB Output is correct
5 Correct 222 ms 18688 KB Output is correct
6 Correct 158 ms 19960 KB Output is correct
7 Correct 143 ms 18912 KB Output is correct
8 Correct 135 ms 20600 KB Output is correct
9 Correct 193 ms 19200 KB Output is correct
10 Correct 152 ms 20344 KB Output is correct
11 Correct 189 ms 21120 KB Output is correct
12 Correct 136 ms 19968 KB Output is correct
13 Correct 138 ms 20088 KB Output is correct
14 Correct 191 ms 20528 KB Output is correct
15 Correct 30 ms 6784 KB Output is correct
16 Correct 194 ms 19612 KB Output is correct
17 Correct 1265 ms 78084 KB Output is correct
18 Correct 744 ms 77876 KB Output is correct
19 Correct 740 ms 78644 KB Output is correct
20 Correct 1053 ms 78728 KB Output is correct
21 Correct 1502 ms 79564 KB Output is correct
22 Correct 1129 ms 79548 KB Output is correct
23 Correct 1064 ms 79296 KB Output is correct
24 Correct 1129 ms 79384 KB Output is correct
25 Correct 879 ms 79452 KB Output is correct
26 Correct 989 ms 79356 KB Output is correct
27 Correct 43 ms 8832 KB Output is correct
28 Correct 187 ms 22904 KB Output is correct
29 Correct 166 ms 23416 KB Output is correct
30 Runtime error 600 ms 49832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -