Submission #100781

#	Time	Username	Problem	Language	Result	Execution time	Memory
100781		Alexa2001	Mecho (IOI09_mecho)	C++17	100 / 100	239 ms	7032 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 808, inf = Nmax * Nmax;
int n, S;
char a[Nmax][Nmax];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

int tmp[Nmax][Nmax], D[Nmax][Nmax];
queue< pair<int,int> > q;


void prec()
{
    int i, j, x, y, X, Y;

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            tmp[i][j] = inf;

    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            if(a[i][j] == 'H')
            {
                q.push({i, j});
                tmp[i][j] = 0;
            }

    while(q.size())
    {
        tie(x, y) = q.front();
        q.pop();

        for(i=0; i<4; ++i)
        {
            X = x + dx[i];
            Y = y + dy[i];

            if((a[X][Y] == 'G' || a[X][Y] == 'M') && tmp[X][Y] == inf)
            {
                tmp[X][Y] = tmp[x][y] + 1;
                q.push({X, Y});
            }
        }
    }
}

bool check(int T)
{
    while(q.size()) q.pop();

    int i, j, x, y, X, Y;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
        {
            if(a[i][j] == 'M')
                x = i, y = j;
            D[i][j] = inf;
        }

    if(!(T < tmp[x][y])) return 0;

    q.push({x, y});
    D[x][y] = 0;

    while(q.size())
    {
        tie(X, Y) = q.front();
        q.pop();

        for(i=0; i<4; ++i)
        {
            x = X + dx[i];
            y = Y + dy[i];

            if(a[x][y] == 'D') return 1;

            if(a[x][y] == 'G' && D[X][Y] + 1 < S * (tmp[x][y] - T) && D[x][y] == inf)
            {
                D[x][y] = D[X][Y] + 1;
                q.push({x, y});
            }
        }
    }
    return 0;
}

int main()
{
//    freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n >> S;
    int i;
    for(i=1; i<=n; ++i) cin >> (a[i] + 1);

    prec();

    int st, dr, mid;
    st = 0; dr = n * n;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(mid)) st = mid + 1;
            else dr = mid - 1;
    }
    cout << dr << '\n';

    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:64:22: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if(!(T < tmp[x][y])) return 0;
              ~~~~~~~~^
mecho.cpp:64:22: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 100 / 100