Submission #1057780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057780		12345678	Mecho (IOI09_mecho)	C++17	10 / 100	167 ms	15556 KiB

mecho

#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], vs[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});
        }
    }
    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]=0, vs[i][j]=0;
        vector<pair<int, int>> cur, nxt;
        vs[st.first][st.second]=1;
        cur.push_back(st);
        int cnt=md;
        while (!cur.empty())
        {
            nxt.clear();
            while (!q.empty()) q.pop();
            for (auto x:cur) if (mn[x.first][x.second]>cnt) q.push(x), dp[x.first][x.second]=s;
            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'||vs[cx][cy]) continue;
                    vs[cx][cy]=1;
                    dp[cx][cy]=dp[x][y]-1;
                    nxt.push_back({cx, cy});
                    if (dp[cx][cy]!=0) q.push({cx, cy});
                }
            }
            cur=nxt;
            cnt++;
        }
        if (vs[tg.first][tg.second]) l=md;
        else r=md-1;
    }
    if (l==0) cout<<-1;
    else cout<<l;
}

• Subtask 1: 10 / 100