Submission #916359

#	Time	Username	Problem	Language	Result	Execution time	Memory
916359		codefox	Mecho (IOI09_mecho)	C++14	100 / 100	269 ms	54284 KiB

mecho

#include<bits/stdc++.h>

using namespace std;


#define pii pair<int, int>
#define piipi pair<pii, int>

int N = 1e6;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, s;
    cin >> n >> s;
    vector<string> grid(n+2);
    string ns = "";
    for (int i = 0; i < n+2; i++) ns += "T";
    grid[0] = ns;
    grid[n+1] = ns;
    for (int i = 1; i <= n; i++) 
    {
        cin >> grid[i];
        grid[i] = "T" + grid[i] + "T";
    }

    vector<vector<int>> graph(N);
    queue<pii> q;
    int home = -1;
    int mecho = -1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int ind = i*(n+2) +j;
            if (grid[i][j]=='H') q.push({0, ind});
            if (grid[i][j]=='D') home = ind;
            if (grid[i][j]=='M') 
            {
                mecho = ind;   
                graph[ind-1].push_back(ind);
                graph[ind+1].push_back(ind);
                graph[ind+n+2].push_back(ind);
                graph[ind-n-2].push_back(ind);
            }
            if (grid[i][j-1]=='G') graph[ind].push_back(ind-1);
            if (grid[i][j+1]=='G') graph[ind].push_back(ind+1);
            if (grid[i+1][j]=='G') graph[ind].push_back(ind+n+2);
            if (grid[i-1][j]=='G') graph[ind].push_back(ind-n-2);
        }
    }

    vector<int> dist(N, -1);
    while (q.size())
    {
        int i, d;
        tie(d, i) = q.front();
        q.pop();
        if (dist[i]!=-1) continue;
        dist[i] = d;
        for (int ele:graph[i])
        {
            q.push({d+1, ele});
        }
    }

    priority_queue<pii, vector<pii>, less<pii>> toadd;
    vector<int> reach(N, 0);
    toadd.push({N, home});
    for (int i = N-1; i >= 0; i--)
    {
        while(toadd.size() && toadd.top().first >= i)
        {
            q.push({0, toadd.top().second});
            toadd.pop();
        }
        while (q.size())
        {
            int j, d;
            tie(d, j) = q.front();
            q.pop();
            if (reach[j]==1) continue;
            reach[j] = 1;
            for (int ele:graph[j])
            {
                if (dist[ele]>=i && d+1 < s) q.push({d+1, ele});
                else toadd.push({dist[ele], ele});
            }
        }
        if (reach[mecho])
        {
            cout << i-1;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

• Subtask 1: 100 / 100