Submission #312953

# Submission time Handle Problem Language Result Execution time Memory
312953 2020-10-14T20:08:32 Z fergonzgut21 Mecho (IOI09_mecho) C++17
37 / 100
381 ms 9088 KB
#include <iostream>
#include <queue>
#define MAX 805
using namespace std;

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

int N, S, sx, sy, ex, ey, B[MAX][MAX], vis[MAX][MAX][2], rilres = -1;
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();
        //cout << temp.x << " " << temp.y << " " << temp.t << " " << temp.r << endl;
        if (temp.x == ex && temp.y == ey)
            rilres = max(rilres,temp.r);
        if (temp.r + (temp.t / S) >= B[temp.x][temp.y])
            temp.r -= ((temp.r + (temp.t / S)) - B[temp.x][temp.y] + 1);
        //cout << temp.x << " " << temp.y << " " << temp.t << " " << temp.r << endl;
        if (temp.r + 2 < rilres)
            break;
        if (temp.r < 0 || temp.r <= rilres)
            continue;
        temp.t++;
        //cout << vis[temp.x][temp.y][0] << " " << vis[temp.x][temp.y][1] << endl;
        if (vis[temp.x + 1][temp.y][1] <= temp.r && A[temp.x + 1][temp.y] != 'T')
        {
            if ((vis[temp.x + 1][temp.y][1] == temp.r && vis[temp.x + 1][temp.y][0] > temp.t) || vis[temp.x + 1][temp.y][1] < temp.r)
            {
                //cout << "SI" << endl;
                vis[temp.x + 1][temp.y][1] = temp.r;
                vis[temp.x + 1][temp.y][0] = temp.t;
                temp.x++;
                qiu2.push(temp);
                temp.x--;
            }
        }
        if (vis[temp.x - 1][temp.y][1] <= temp.r && A[temp.x - 1][temp.y] != 'T')
        {
            if ((vis[temp.x - 1][temp.y][1] == temp.r && vis[temp.x - 1][temp.y][0] > temp.t) || vis[temp.x - 1][temp.y][1] < temp.r)
            {
                vis[temp.x - 1][temp.y][1] = temp.r;
                vis[temp.x - 1][temp.y][0] = temp.t;
                temp.x--;
                qiu2.push(temp);
                temp.x++;
            }
        }
        if (vis[temp.x][temp.y + 1][1] <= temp.r && A[temp.x][temp.y + 1] != 'T')
        {
            if ((vis[temp.x][temp.y + 1][1] == temp.r && vis[temp.x][temp.y + 1][0] > temp.t) || vis[temp.x][temp.y + 1][1] < temp.r)
            {
                vis[temp.x][temp.y + 1][1] = temp.r;
                vis[temp.x][temp.y + 1][0] = temp.t;
                temp.y++;
                qiu2.push(temp);
                temp.y--;
            }
        }
        if (vis[temp.x][temp.y - 1][1] <= temp.r && A[temp.x][temp.y - 1] != 'T')
        {
            if ((vis[temp.x][temp.y - 1][1] == temp.r && vis[temp.x][temp.y - 1][0] > temp.t) || vis[temp.x][temp.y - 1][1] < temp.r)
            {
                vis[temp.x][temp.y - 1][1] = temp.r;
                vis[temp.x][temp.y - 1][0] = temp.t;
                temp.y--;
                qiu2.push(temp);
                temp.y++;
            }
        }
    }
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> S;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
        {
            cin >> A[i][j];
            vis[i][j][1] = -1;
            vis[i][j][0] = 32700;
            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][1] = 32700;
    vis[sx][sy][0] = 0;
    solve2(sx, sy, 0, B[sx][sy] - 1);
    cout << rilres;
    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 0 ms 384 KB Output isn't correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Correct 1 ms 384 KB Output is correct
6 Incorrect 1 ms 384 KB Output isn't correct
7 Incorrect 29 ms 8704 KB Output isn't correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Incorrect 0 ms 512 KB Output isn't correct
11 Incorrect 1 ms 512 KB Output isn't correct
12 Correct 1 ms 896 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 896 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 512 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 1 ms 640 KB Output is correct
21 Correct 1 ms 640 KB Output is correct
22 Correct 1 ms 640 KB Output is correct
23 Correct 1 ms 768 KB Output is correct
24 Correct 1 ms 768 KB Output is correct
25 Correct 1 ms 896 KB Output is correct
26 Correct 1 ms 896 KB Output is correct
27 Correct 1 ms 896 KB Output is correct
28 Correct 1 ms 896 KB Output is correct
29 Correct 1 ms 896 KB Output is correct
30 Correct 1 ms 896 KB Output is correct
31 Correct 1 ms 1024 KB Output is correct
32 Correct 1 ms 1024 KB Output is correct
33 Correct 6 ms 3968 KB Output is correct
34 Correct 5 ms 3968 KB Output is correct
35 Incorrect 30 ms 4088 KB Output isn't correct
36 Correct 7 ms 4480 KB Output is correct
37 Correct 7 ms 4480 KB Output is correct
38 Incorrect 44 ms 4608 KB Output isn't correct
39 Correct 9 ms 4992 KB Output is correct
40 Correct 8 ms 4992 KB Output is correct
41 Incorrect 62 ms 5112 KB Output isn't correct
42 Correct 10 ms 5504 KB Output is correct
43 Correct 9 ms 5504 KB Output is correct
44 Incorrect 84 ms 5624 KB Output isn't correct
45 Correct 12 ms 6144 KB Output is correct
46 Correct 11 ms 6016 KB Output is correct
47 Incorrect 115 ms 6264 KB Output isn't correct
48 Correct 14 ms 6656 KB Output is correct
49 Correct 12 ms 6528 KB Output is correct
50 Incorrect 146 ms 6776 KB Output isn't correct
51 Correct 15 ms 7040 KB Output is correct
52 Correct 14 ms 7040 KB Output is correct
53 Incorrect 184 ms 7396 KB Output isn't correct
54 Correct 18 ms 7552 KB Output is correct
55 Correct 16 ms 7552 KB Output is correct
56 Incorrect 227 ms 7928 KB Output isn't correct
57 Correct 20 ms 8064 KB Output is correct
58 Correct 18 ms 8060 KB Output is correct
59 Incorrect 277 ms 8440 KB Output isn't correct
60 Correct 22 ms 8576 KB Output is correct
61 Correct 20 ms 8576 KB Output is correct
62 Incorrect 337 ms 9036 KB Output isn't correct
63 Incorrect 30 ms 8576 KB Output isn't correct
64 Incorrect 45 ms 8576 KB Output isn't correct
65 Incorrect 30 ms 8576 KB Output isn't correct
66 Incorrect 30 ms 8608 KB Output isn't correct
67 Correct 30 ms 8576 KB Output is correct
68 Incorrect 32 ms 8652 KB Output isn't correct
69 Incorrect 34 ms 8576 KB Output isn't correct
70 Incorrect 32 ms 8576 KB Output isn't correct
71 Incorrect 32 ms 8576 KB Output isn't correct
72 Correct 32 ms 8576 KB Output is correct
73 Correct 35 ms 8960 KB Output is correct
74 Correct 65 ms 8960 KB Output is correct
75 Correct 36 ms 8960 KB Output is correct
76 Correct 36 ms 8960 KB Output is correct
77 Correct 36 ms 9088 KB Output is correct
78 Correct 65 ms 8960 KB Output is correct
79 Incorrect 277 ms 9080 KB Output isn't correct
80 Incorrect 335 ms 9080 KB Output isn't correct
81 Incorrect 222 ms 8960 KB Output isn't correct
82 Incorrect 105 ms 8960 KB Output isn't correct
83 Incorrect 31 ms 8832 KB Output isn't correct
84 Incorrect 245 ms 8832 KB Output isn't correct
85 Incorrect 175 ms 8832 KB Output isn't correct
86 Incorrect 170 ms 8832 KB Output isn't correct
87 Incorrect 124 ms 8948 KB Output isn't correct
88 Correct 217 ms 9056 KB Output is correct
89 Incorrect 381 ms 8952 KB Output isn't correct
90 Incorrect 121 ms 8832 KB Output isn't correct
91 Incorrect 349 ms 9080 KB Output isn't correct
92 Incorrect 255 ms 8960 KB Output isn't correct