답안 #312935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
312935	2020-10-14T19:02:16 Z	fergonzgut21	Mecho (IOI09_mecho)	C++14	9 / 100	1000 ms	8424 KB

mecho

#include <iostream>
#include <queue>
#define MAX 805
using namespace std;

struct bee
{
    int x;
    int y;
    int t;
    int r;
};

int N, S, sx, sy, ex, ey, B[MAX][MAX], vis[MAX][MAX];
char A[MAX][MAX];
queue <bee> qiu, qiu2;
bee temp;

void solve ()
{
    while (!qiu.empty())
    {
        temp = qiu.front();
        qiu.pop();
        temp.t++;
        if (B[temp.x - 1][temp.y] == -1 && A[temp.x - 1][temp.y] != 'T' && A[temp.x - 1][temp.y] != 'D')
        {
            B[temp.x - 1][temp.y] = temp.t;
            temp.x--;
            qiu.push(temp);
            temp.x++;
        }
        if (B[temp.x + 1][temp.y] == -1 && A[temp.x + 1][temp.y] != 'T' && A[temp.x + 1][temp.y] != 'D')
        {
            B[temp.x + 1][temp.y] = temp.t;
            temp.x++;
            qiu.push(temp);
            temp.x--;
        }
        if (B[temp.x][temp.y - 1] == -1 && A[temp.x][temp.y - 1] != 'T' && A[temp.x][temp.y - 1] != 'D')
        {
            B[temp.x][temp.y - 1] = temp.t;
            temp.y--;
            qiu.push(temp);
            temp.y++;
        }
        if (B[temp.x][temp.y + 1] == -1 && A[temp.x][temp.y + 1] != 'T' && A[temp.x][temp.y + 1] != 'D')
        {
            B[temp.x][temp.y + 1] = temp.t;
            temp.y++;
            qiu.push(temp);
            temp.y--;
        }
    }
}

int solve2(int x, int y, int t, int r)
{
    temp.x = x;
    temp.y = y;
    temp.t = t;
    temp.r = r;
    qiu2.push(temp);
    while (!qiu2.empty())
    {
        temp = qiu2.front();
        qiu2.pop();
        if (temp.x == ex && temp.y == ey)
            return temp.r;
        //cout << temp.x << " " << temp.y << " " << temp.t << " " << temp.r << endl;
        if (temp.r + (temp.t / S) >= B[x][y])
            temp.r -= (temp.r + (temp.t / S)) - B[x][y] + 1;
        if (temp.r < 0)
            continue;
        temp.t++;
        if (vis[temp.x + 1][temp.y] > temp.r && A[temp.x + 1][temp.y] != 'T')
        {
            vis[temp.x + 1][temp.y] = temp.r;
            temp.x++;
            qiu2.push(temp);
            temp.x--;
        }
        if (vis[temp.x - 1][temp.y] > temp.r && A[temp.x - 1][temp.y] != 'T')
        {
            vis[temp.x - 1][temp.y] = temp.r;
            temp.x--;
            qiu2.push(temp);
            temp.x++;
        }
        if (vis[temp.x][temp.y + 1] > temp.r && A[temp.x][temp.y + 1] != 'T')
        {
            vis[temp.x][temp.y + 1] = temp.r;
            temp.y++;
            qiu2.push(temp);
            temp.y--;
        }
        if (vis[temp.x][temp.y - 1] > temp.r && A[temp.x][temp.y - 1] != 'T')
        {
            vis[temp.x][temp.y - 1] = temp.r;
            temp.y--;
            qiu2.push(temp);
            temp.y++;
        }
    }
    return -1;
}

int main()
{
    cin >> N >> S;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            cin >> A[i][j];
            vis[i][j] =1073741822;
            B[i][j] = -1;
            if (A[i][j] == 'M')
            {
                sx = i;
                sy = j;
            }
            if (A[i][j] == 'D')
            {
                ex = i;
                ey = j;
            }
            if (A[i][j] == 'H')
            {
                temp.x = i;
                temp.y = j;
                temp.t = 0;
                B[i][j] = 0;
                qiu.push(temp);
            }
        }
    solve();
    /*cout << endl;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cout << B[i][j] << " ";
        }
        cout << endl;
    }*/
    vis[sx][sy] = 0;
    cout << solve2(sx, sy, 0, B[sx][sy] - 1) - 1;
    return 0;
}

Subtask #1

9.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	384 KB	Output isn't correct
2	Incorrect	1 ms	384 KB	Output isn't correct
3	Incorrect	0 ms	384 KB	Output isn't correct
4	Incorrect	0 ms	384 KB	Output isn't correct
5	Incorrect	1 ms	384 KB	Output isn't correct
6	Incorrect	1 ms	384 KB	Output isn't correct
7	Incorrect	190 ms	6904 KB	Output isn't correct
8	Incorrect	1 ms	384 KB	Output isn't correct
9	Incorrect	1 ms	384 KB	Output isn't correct
10	Incorrect	1 ms	512 KB	Output isn't correct
11	Incorrect	1 ms	384 KB	Output isn't correct
12	Incorrect	1 ms	768 KB	Output isn't correct
13	Incorrect	1 ms	768 KB	Output isn't correct
14	Incorrect	1 ms	768 KB	Output isn't correct
15	Correct	1 ms	512 KB	Output is correct
16	Incorrect	1 ms	512 KB	Output isn't correct
17	Correct	1 ms	512 KB	Output is correct
18	Incorrect	1 ms	512 KB	Output isn't correct
19	Correct	1 ms	512 KB	Output is correct
20	Incorrect	1 ms	512 KB	Output isn't correct
21	Correct	1 ms	512 KB	Output is correct
22	Incorrect	1 ms	640 KB	Output isn't correct
23	Correct	1 ms	640 KB	Output is correct
24	Incorrect	1 ms	640 KB	Output isn't correct
25	Correct	1 ms	768 KB	Output is correct
26	Incorrect	1 ms	768 KB	Output isn't correct
27	Correct	1 ms	768 KB	Output is correct
28	Incorrect	1 ms	768 KB	Output isn't correct
29	Correct	1 ms	896 KB	Output is correct
30	Incorrect	1 ms	896 KB	Output isn't correct
31	Correct	1 ms	896 KB	Output is correct
32	Incorrect	1 ms	896 KB	Output isn't correct
33	Correct	13 ms	2944 KB	Output is correct
34	Incorrect	13 ms	2944 KB	Output isn't correct
35	Incorrect	15 ms	2944 KB	Output isn't correct
36	Correct	17 ms	3328 KB	Output is correct
37	Incorrect	16 ms	3328 KB	Output isn't correct
38	Incorrect	19 ms	3328 KB	Output isn't correct
39	Correct	21 ms	3712 KB	Output is correct
40	Incorrect	20 ms	3704 KB	Output isn't correct
41	Incorrect	24 ms	3712 KB	Output isn't correct
42	Correct	26 ms	4088 KB	Output is correct
43	Incorrect	25 ms	4096 KB	Output isn't correct
44	Incorrect	29 ms	4096 KB	Output isn't correct
45	Correct	31 ms	4516 KB	Output is correct
46	Incorrect	30 ms	4516 KB	Output isn't correct
47	Incorrect	36 ms	4576 KB	Output isn't correct
48	Correct	37 ms	4984 KB	Output is correct
49	Incorrect	36 ms	4984 KB	Output isn't correct
50	Incorrect	41 ms	4984 KB	Output isn't correct
51	Correct	41 ms	5368 KB	Output is correct
52	Incorrect	40 ms	5368 KB	Output isn't correct
53	Incorrect	48 ms	5372 KB	Output isn't correct
54	Correct	49 ms	5880 KB	Output is correct
55	Incorrect	46 ms	5752 KB	Output isn't correct
56	Incorrect	56 ms	5752 KB	Output isn't correct
57	Correct	55 ms	6264 KB	Output is correct
58	Incorrect	53 ms	6136 KB	Output isn't correct
59	Incorrect	63 ms	6264 KB	Output isn't correct
60	Correct	61 ms	6648 KB	Output is correct
61	Incorrect	60 ms	6648 KB	Output isn't correct
62	Incorrect	72 ms	6648 KB	Output isn't correct
63	Execution timed out	1091 ms	7616 KB	Time limit exceeded
64	Incorrect	94 ms	6648 KB	Output isn't correct
65	Execution timed out	1090 ms	7884 KB	Time limit exceeded
66	Execution timed out	1081 ms	8080 KB	Time limit exceeded
67	Execution timed out	1090 ms	7624 KB	Time limit exceeded
68	Incorrect	410 ms	6904 KB	Output isn't correct
69	Incorrect	134 ms	6780 KB	Output isn't correct
70	Incorrect	823 ms	7428 KB	Output isn't correct
71	Execution timed out	1089 ms	7424 KB	Time limit exceeded
72	Incorrect	73 ms	6648 KB	Output isn't correct
73	Incorrect	71 ms	7160 KB	Output isn't correct
74	Incorrect	80 ms	7164 KB	Output isn't correct
75	Incorrect	382 ms	8000 KB	Output isn't correct
76	Incorrect	513 ms	8424 KB	Output isn't correct
77	Incorrect	255 ms	7320 KB	Output isn't correct
78	Incorrect	347 ms	7556 KB	Output isn't correct
79	Incorrect	81 ms	7160 KB	Output isn't correct
80	Incorrect	340 ms	7636 KB	Output isn't correct
81	Incorrect	459 ms	8104 KB	Output isn't correct
82	Incorrect	220 ms	7160 KB	Output isn't correct
83	Incorrect	435 ms	7720 KB	Output isn't correct
84	Incorrect	86 ms	7160 KB	Output isn't correct
85	Incorrect	266 ms	7160 KB	Output isn't correct
86	Incorrect	351 ms	7484 KB	Output isn't correct
87	Incorrect	187 ms	7032 KB	Output isn't correct
88	Incorrect	290 ms	7292 KB	Output isn't correct
89	Incorrect	84 ms	6904 KB	Output isn't correct
90	Incorrect	194 ms	6936 KB	Output isn't correct
91	Incorrect	142 ms	7032 KB	Output isn't correct
92	Incorrect	246 ms	7132 KB	Output isn't correct