oj.uz

답안 #391391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
391391 2021-04-18T16:47:48 Z ml1234 Mecho (IOI09_mecho) C++17
27 / 100
 1000 ms 8644 KB 
#include <iostream>
#include <string>
#include <queue>
using namespace std;
void floodfillbees(int i, int j);
bool validmecho(int i, int j);

string grid[800];
int bees[800][800];
int dx[] = {0, -1, 1, 0}, dy[] = {-1, 0, 0, 1};
int n, s;
int main() 
{
    cin >> n >> s;
    pair<int, int> mecho = {0, 0};
    int mechodist[800][800], mindiff[800][800]{};
    for (int i = 0; i < n; i++)
    {
        cin >> grid[i];
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 'M')
            {
                mecho = {i, j};
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            bees[i][j] = 1e9;
            mechodist[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 'H')
            {
                floodfillbees(i, j);
            }
        }
    }
    queue<pair<int, int>> q;
    q.push(mecho);
    mechodist[mecho.first][mecho.second] = 0;
    mindiff[mecho.first][mecho.second] = bees[mecho.first][mecho.second];
    int ans = 0;
    while (!q.empty())
    {
        int curri = q.front().first, currj = q.front().second;
        q.pop();
        if (grid[curri][currj] == 'D')
        {
            if (mindiff[curri][currj] > 0)
            {
                ans = max(ans, mindiff[curri][currj] / s);
            }
            continue;
        }
        for (int d = 0; d < 4; d++)
        {
            int nexti = curri + dx[d], nextj = currj + dy[d];
            if (!validmecho(nexti, nextj))
            {
                continue;
            }
            if (mechodist[nexti][nextj] == -1)
            {
                mechodist[nexti][nextj] = mechodist[curri][currj] + 1;
                mindiff[nexti][nextj] = min(mindiff[curri][currj], bees[nexti][nextj] - mechodist[nexti][nextj]);
                q.push({nexti, nextj});
            }
        }
    }
    cout << ans << endl;
    return 0;
}

bool ongrid(int i, int j)
{
    return (i >= 0 && i < n && j >= 0 && j < n);
}
bool validbees(int i, int j)
{
    return (ongrid(i, j) && !(grid[i][j] == 'T') && !(grid[i][j] == 'D') && !(grid[i][j] == 'H'));
}
bool validmecho(int i, int j)
{
    return (ongrid(i, j) && !(grid[i][j] == 'T'));
}

void floodfillbees(int i, int j)
{
    queue<pair<int, int>> q;
    q.push({i, j});
    bees[i][j] = 0;
    while (!q.empty())
    {
        int curri = q.front().first, currj = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++)
        {
            int nexti = curri + dx[d], nextj = currj + dy[d];
            if (validbees(nexti, nextj) && bees[nexti][nextj] > bees[curri][currj] + s)
            {
                bees[nexti][nextj] = bees[curri][currj] + s;
                q.push({nexti, nextj});
            }
        }
    }
}

Subtask #1
27.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2764 KB Output isn't correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Incorrect 2 ms 2764 KB Output isn't correct
4 Incorrect 2 ms 2764 KB Output isn't correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2892 KB Output is correct
7 Correct 290 ms 8588 KB Output is correct
8 Incorrect 2 ms 2892 KB Output isn't correct
9 Correct 2 ms 2892 KB Output is correct
10 Correct 2 ms 2896 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Incorrect 2 ms 3148 KB Output isn't correct
13 Correct 3 ms 3148 KB Output is correct
14 Incorrect 4 ms 3148 KB Output isn't correct
15 Incorrect 2 ms 2892 KB Output isn't correct
16 Correct 2 ms 2892 KB Output is correct
17 Incorrect 2 ms 2892 KB Output isn't correct
18 Correct 2 ms 2892 KB Output is correct
19 Incorrect 2 ms 3020 KB Output isn't correct
20 Correct 2 ms 3020 KB Output is correct
21 Incorrect 2 ms 3020 KB Output isn't correct
22 Correct 2 ms 3020 KB Output is correct
23 Incorrect 2 ms 3020 KB Output isn't correct
24 Correct 2 ms 3020 KB Output is correct
25 Incorrect 3 ms 3148 KB Output isn't correct
26 Correct 2 ms 3148 KB Output is correct
27 Incorrect 2 ms 3148 KB Output isn't correct
28 Correct 2 ms 3148 KB Output is correct
29 Incorrect 2 ms 3276 KB Output isn't correct
30 Correct 2 ms 3276 KB Output is correct
31 Incorrect 3 ms 3276 KB Output isn't correct
32 Correct 2 ms 3276 KB Output is correct
33 Incorrect 11 ms 5196 KB Output isn't correct
34 Correct 13 ms 5196 KB Output is correct
35 Incorrect 15 ms 5200 KB Output isn't correct
36 Incorrect 12 ms 5452 KB Output isn't correct
37 Correct 14 ms 5452 KB Output is correct
38 Incorrect 20 ms 5532 KB Output isn't correct
39 Incorrect 14 ms 5868 KB Output isn't correct
40 Correct 16 ms 5860 KB Output is correct
41 Incorrect 25 ms 5764 KB Output isn't correct
42 Incorrect 18 ms 6348 KB Output isn't correct
43 Correct 20 ms 6332 KB Output is correct
44 Incorrect 29 ms 6444 KB Output isn't correct
45 Incorrect 20 ms 6732 KB Output isn't correct
46 Correct 23 ms 6812 KB Output is correct
47 Incorrect 35 ms 6732 KB Output isn't correct
48 Incorrect 24 ms 7092 KB Output isn't correct
49 Correct 27 ms 7116 KB Output is correct
50 Incorrect 41 ms 7116 KB Output isn't correct
51 Incorrect 28 ms 7500 KB Output isn't correct
52 Correct 31 ms 7496 KB Output is correct
53 Incorrect 48 ms 7508 KB Output isn't correct
54 Incorrect 31 ms 7804 KB Output isn't correct
55 Correct 36 ms 7868 KB Output is correct
56 Incorrect 55 ms 7764 KB Output isn't correct
57 Incorrect 36 ms 8220 KB Output isn't correct
58 Correct 40 ms 8228 KB Output is correct
59 Incorrect 63 ms 8244 KB Output isn't correct
60 Incorrect 42 ms 8596 KB Output isn't correct
61 Correct 45 ms 8532 KB Output is correct
62 Incorrect 71 ms 8588 KB Output isn't correct
63 Correct 119 ms 8576 KB Output is correct
64 Correct 110 ms 8524 KB Output is correct
65 Correct 132 ms 8592 KB Output is correct
66 Incorrect 125 ms 8528 KB Output isn't correct
67 Incorrect 122 ms 8644 KB Output isn't correct
68 Correct 313 ms 8576 KB Output is correct
69 Correct 304 ms 8516 KB Output is correct
70 Correct 312 ms 8584 KB Output is correct
71 Correct 307 ms 8576 KB Output is correct
72 Incorrect 302 ms 8524 KB Output isn't correct
73 Execution timed out 1080 ms 8524 KB Time limit exceeded
74 Execution timed out 1086 ms 8524 KB Time limit exceeded
75 Execution timed out 1092 ms 8524 KB Time limit exceeded
76 Execution timed out 1092 ms 8504 KB Time limit exceeded
77 Execution timed out 1040 ms 8516 KB Time limit exceeded
78 Execution timed out 1069 ms 8524 KB Time limit exceeded
79 Execution timed out 1094 ms 8528 KB Time limit exceeded
80 Execution timed out 1092 ms 8536 KB Time limit exceeded
81 Execution timed out 1102 ms 8524 KB Time limit exceeded
82 Execution timed out 1090 ms 8496 KB Time limit exceeded
83 Correct 420 ms 8644 KB Output is correct
84 Correct 417 ms 8584 KB Output is correct
85 Correct 419 ms 8588 KB Output is correct
86 Incorrect 423 ms 8584 KB Output isn't correct
87 Correct 435 ms 8584 KB Output is correct
88 Correct 339 ms 8584 KB Output is correct
89 Correct 331 ms 8584 KB Output is correct
90 Correct 364 ms 8636 KB Output is correct
91 Correct 343 ms 8588 KB Output is correct
92 Correct 337 ms 8600 KB Output is correct