답안 #93234 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93234	2019-01-07T10:25:27 Z	Alexa2001	Golf (JOI17_golf)	C++17	30 / 100	1502 ms	79564 KB

golf

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #93234

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 70.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 70.0