Submission #242012

#	Time	Username	Problem	Language	Result	Execution time	Memory
242012		Autoratch	Mecho (IOI09_mecho)	C++14	19 / 100	444 ms	4600 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

const int N = 801;

int n,s,sx,sy,tx,ty;
char c[N][N];
int bee[N][N];
bool visited[N][N];
queue<pair<pair<int,int>,int> > qb,q;

void flybee()
{
    while(!qb.empty())
    {
        int t = qb.front().second,x = qb.front().first.first,y = qb.front().first.second;
        qb.pop();
        for(int i = -1;i <= 1;i++) for(int j = -1;j <= 1;j++)
        {
            if(i!=0 and j!=0) continue;
            if(i==0 and j==0) continue;
            int ai = x+i,aj = y+j;
            if(ai<1 or ai>n or aj<1 or aj>n) continue;
            if(c[ai][aj]=='D' or c[ai][aj]=='T') continue;
            if(visited[ai][aj]) continue;
            visited[ai][aj] = true;
            bee[ai][aj] = t+1;
            qb.push({{ai,aj},t+1});
        }
    }
}

bool solve(int x)
{
    for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) visited[i][j] = false;
    while(!q.empty()) q.pop();
    q.push({{sx,sy},x});
    visited[sx][sy] = true;
    while(!q.empty())
    {
        int x = q.front().first.first,y = q.front().first.second,tm = q.front().second;
        q.pop();
        if(x==tx and y==ty) return true;
        for(int i = -1;i <= 1;i++) for(int j = -1;j <= 1;j++)
        {
            if(i!=0 and j!=0) continue;
            if(i==0 and j==0) continue;
            int ai = x+i,aj = y+j;
            if(ai<1 or ai>n or aj<1 or aj>n) continue;
            if(c[ai][aj]=='T') continue;
            if(visited[ai][aj]) continue;
            if(tm+1>=bee[ai][aj]*s) continue;
            q.push({{ai,aj},tm+1});
            visited[ai][aj] = true;
        }
    }
    return false;
}

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 >> c[i][j],bee[i][j] = INT_MAX;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) 
        if(c[i][j]=='H') qb.push({{i,j},0}),bee[i][j] = 0,visited[i][j] = true; 
        else if(c[i][j]=='M') sx = i,sy = j;
        else if(c[i][j]=='D') tx = i,ty = j;
    flybee();
    int l = 0,r = n*n;
    while(l<r)
    {
        int m = (l+r+1)/2;
        if(solve(m)) l = m;
        else r = m-1;
    }
    if(solve(l)) cout << l;
    else cout << "-1";
}

• Subtask 1: 19 / 100