답안 #957974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957974 2024-04-04T15:21:07 Z 12345678 Mecho (IOI09_mecho) C++17
26 / 100
127 ms 6992 KB
#include <bits/stdc++.h>

using namespace std;

const int nx=805;

int n, s, mn[nx][nx], dx[4]={1, 0, 0, -1}, dy[4]={0, 1, -1, 0}, dp[nx][nx];
char mp[nx][nx];
pair<int, int> st, tg;
queue<pair<int, int>> q;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) cin>>mp[i][j], mn[i][j]=1e9;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='M') st={i, j};
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='H') q.push({i, j}), mn[i][j]=0;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='D') tg={i, j};
    while (!q.empty())
    {
        auto [x, y]=q.front();
        q.pop();
        for (int i=0; i<4; i++)
        {
            int cx=x+dx[i], cy=y+dy[i];
            if (cx<1||cx>n||cy<1||cy>n||mp[cx][cy]=='T'||mp[cx][cy]=='D') continue;
            if (mn[cx][cy]>mn[x][y]+1) mn[cx][cy]=mn[x][y]+1, q.push({cx, cy});
        }
    }
    /*
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++) cout<<mn[i][j]<<' ';
        cout<<'\n';
    }
    */
    int l=0, r=2*n;
    while (l<r)
    {
        int md=(l+r+1)/2;
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j]=1e9;
        if (mn[st.first][st.second]<=md)
        {
            r=md-1;
            continue;
        }
        dp[st.first][st.second]=0;
        q.push({st.first, st.second});
        while (!q.empty())
        {
            auto [x, y]=q.front();
            q.pop();
            for (int i=0; i<4; i++)
            {
                int cx=x+dx[i], cy=y+dy[i];
                if (cx<1||cx>n||cy<1||cy>n||mp[cx][cy]=='T'||mp[cx][cy]=='H') continue;
                if (dp[cx][cy]>dp[x][y]+1&&(md+(dp[x][y])/s)<mn[cx][cy]) dp[cx][cy]=dp[x][y]+1, q.push({cx, cy});
            }
        }
        /*
        cout<<"debug "<<md<<'\n';
        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++) cout<<dp[i][j]<<' ';
            cout<<'\n';
        }*/
        if (dp[tg.first][tg.second]!=1e9) l=md;
        else r=md-1;
    }
    if (l==0) cout<<-1;
    else cout<<l;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Incorrect 2 ms 4440 KB Output isn't correct
3 Incorrect 2 ms 4444 KB Output isn't correct
4 Incorrect 2 ms 4560 KB Output isn't correct
5 Incorrect 1 ms 4440 KB Output isn't correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 67 ms 6296 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Incorrect 1 ms 4444 KB Output isn't correct
13 Incorrect 1 ms 4444 KB Output isn't correct
14 Correct 1 ms 4444 KB Output is correct
15 Incorrect 1 ms 4700 KB Output isn't correct
16 Incorrect 1 ms 4444 KB Output isn't correct
17 Incorrect 1 ms 4444 KB Output isn't correct
18 Incorrect 1 ms 4444 KB Output isn't correct
19 Incorrect 1 ms 4444 KB Output isn't correct
20 Incorrect 1 ms 4444 KB Output isn't correct
21 Incorrect 1 ms 4444 KB Output isn't correct
22 Incorrect 1 ms 4444 KB Output isn't correct
23 Incorrect 1 ms 4444 KB Output isn't correct
24 Incorrect 1 ms 4444 KB Output isn't correct
25 Incorrect 1 ms 4444 KB Output isn't correct
26 Incorrect 1 ms 4444 KB Output isn't correct
27 Incorrect 2 ms 4444 KB Output isn't correct
28 Incorrect 2 ms 4444 KB Output isn't correct
29 Incorrect 2 ms 4444 KB Output isn't correct
30 Incorrect 2 ms 4440 KB Output isn't correct
31 Incorrect 1 ms 4632 KB Output isn't correct
32 Incorrect 1 ms 4444 KB Output isn't correct
33 Incorrect 14 ms 4700 KB Output isn't correct
34 Incorrect 13 ms 4700 KB Output isn't correct
35 Correct 18 ms 4696 KB Output is correct
36 Incorrect 13 ms 4952 KB Output isn't correct
37 Incorrect 27 ms 4956 KB Output isn't correct
38 Correct 23 ms 4984 KB Output is correct
39 Incorrect 17 ms 4956 KB Output isn't correct
40 Incorrect 21 ms 4956 KB Output isn't correct
41 Correct 35 ms 5092 KB Output is correct
42 Incorrect 20 ms 5384 KB Output isn't correct
43 Incorrect 26 ms 5404 KB Output isn't correct
44 Correct 33 ms 5212 KB Output is correct
45 Incorrect 25 ms 5468 KB Output isn't correct
46 Incorrect 34 ms 5468 KB Output isn't correct
47 Correct 41 ms 5468 KB Output is correct
48 Incorrect 30 ms 5764 KB Output isn't correct
49 Incorrect 56 ms 5724 KB Output isn't correct
50 Correct 48 ms 5728 KB Output is correct
51 Incorrect 36 ms 5968 KB Output isn't correct
52 Incorrect 49 ms 5720 KB Output isn't correct
53 Correct 71 ms 5980 KB Output is correct
54 Incorrect 41 ms 6096 KB Output isn't correct
55 Incorrect 55 ms 6152 KB Output isn't correct
56 Correct 72 ms 6140 KB Output is correct
57 Incorrect 50 ms 6288 KB Output isn't correct
58 Incorrect 61 ms 6344 KB Output isn't correct
59 Correct 85 ms 6236 KB Output is correct
60 Incorrect 52 ms 6492 KB Output isn't correct
61 Incorrect 71 ms 6540 KB Output isn't correct
62 Correct 110 ms 6552 KB Output is correct
63 Incorrect 85 ms 6528 KB Output isn't correct
64 Correct 127 ms 6524 KB Output is correct
65 Correct 112 ms 6584 KB Output is correct
66 Incorrect 88 ms 6516 KB Output isn't correct
67 Correct 85 ms 6488 KB Output is correct
68 Incorrect 37 ms 6488 KB Output isn't correct
69 Correct 35 ms 6492 KB Output is correct
70 Correct 32 ms 6488 KB Output is correct
71 Correct 32 ms 6492 KB Output is correct
72 Correct 28 ms 6488 KB Output is correct
73 Correct 32 ms 6740 KB Output is correct
74 Correct 45 ms 6744 KB Output is correct
75 Correct 57 ms 6880 KB Output is correct
76 Correct 50 ms 6652 KB Output is correct
77 Correct 53 ms 6852 KB Output is correct
78 Correct 63 ms 6796 KB Output is correct
79 Correct 50 ms 6740 KB Output is correct
80 Correct 58 ms 6992 KB Output is correct
81 Correct 57 ms 6744 KB Output is correct
82 Correct 58 ms 6744 KB Output is correct
83 Incorrect 60 ms 6748 KB Output isn't correct
84 Correct 57 ms 6488 KB Output is correct
85 Correct 58 ms 6748 KB Output is correct
86 Correct 61 ms 6748 KB Output is correct
87 Correct 55 ms 6748 KB Output is correct
88 Incorrect 63 ms 6740 KB Output isn't correct
89 Correct 64 ms 6492 KB Output is correct
90 Correct 66 ms 6652 KB Output is correct
91 Correct 67 ms 6872 KB Output is correct
92 Correct 74 ms 6744 KB Output is correct