Submission #882643

#	Time	Username	Problem	Language	Result	Execution time	Memory
882643		qrupafjzvm1	Mecho (IOI09_mecho)	C++14	0 / 100	1102 ms	65536 KiB

mecho

//memset 0x3f -> > 1000000000
#include <bits/stdc++.h>
#define f first
#define s second
#define MAXSIZE (int)(2e5+5)
// #define int long long
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef pair<int,int> ii;
string answerString[2] = {"NO", "YES"};
int add(int x, int y, int mod)
{
    int t = x + y;
    return t - mod * (t>=mod);
}
int sub(int x, int y, int mod)
{
    int t = x - y;
    return t + mod * (t<0);
}
int xd[4] = {0,0,1,-1}, yd[4] = {1,-1,0,0};
int d[808][808];
char c[808][808];
bool ch[808][808];
int mx, my, dx, dy, n, s;
vector <ii> hives;
void bfs()
{
    queue <ii> q;
    memset(d,0x3f,sizeof(d));
    for (ii h : hives) {q.push(h); d[h.f][h.s] = 0;}
    while (!q.empty())
    {
        ii u = q.front(); q.pop();
        for (int i=0;i<4;i++)
        {
            ii v = {u.f + xd[i], u.s + yd[i]};
            if (v.f>=1 && v.f<=n && v.s>=1 && v.s<=n
            && c[v.f][v.s] == 'G' && d[v.f][v.s]>d[u.f][u.s]+1)
            {
                d[v.f][v.s] = d[u.f][u.s] + 1;
                q.push(v);
            }
        }
    }
}
void dfs(int x, int y, int dt, int cnt)
{
    ch[x][y] = true;
    for (int i=0;i<4;i++)
    {
        int nx = x + xd[i], ny = y + yd[i];
        if (nx>=1 && nx<=n && ny>=1 && ny<=n
        && c[nx][ny] != 'T' && dt+(cnt==0)<d[nx][ny])
        {
            if (cnt==0) dfs(nx,ny,dt+1,s-1);
            else dfs(nx,ny,dt,cnt-1);
        }
    }
}
signed main()
{
    //freopen("mecho.inp","r",stdin);
    //freopen("text.out","w",stdout);
    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];
            if (c[i][j]=='M') {mx = i, my = j;}
            if (c[i][j]=='D') {dx = i, dy = j;}
            if (c[i][j]=='H') hives.push_back({i,j});
        }
    bfs();
    /*for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++) cout<<d[i][j]<<" ";
        cout<<endl;
    }*/
    int l = -1, r = n*n+1, ans = -1;
    while (r-l>1)
    {
        memset(ch,0,sizeof(ch));
        //cout<<l<<" "<<r<<endl;
        int m = (l + r) / 2; dfs(mx, my, m, s);
        if (ch[dx][dy]) l = ans = m;
        else r = m;
    }
    memset(ch,0,sizeof(ch));
    dfs(mx, my, l, s);
    if (ch[dx][dy]) cout<<l;
    else cout<<-1;
}

• Subtask 1: 0 / 100