Submission #843767

#	Time	Username	Problem	Language	Result	Execution time	Memory
843767		saturina	Mecho (IOI09_mecho)	C++14	84 / 100	656 ms	6992 KiB

mecho

//made by Nguyễn Hồng Nam
#include <bits/stdc++.h>
using namespace std;
#define ll int
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pll pair<ll,ll>
#define fi first
#define se second
const ll mod = 1e9 + 7,inf = 1e9,mxn = 805;
string s[mxn];
ll n,step,ans = inf,bear[mxn][mxn],bee[mxn][mxn],row[4] = {-1,0,0,1},col[4] = {0,-1,1,0},inf2;
pll start,en;
bool mark[mxn][mxn];
void minz(ll &a,ll b)
{
    if(a > b ) a = b;
}
bool check_bee(ll a,ll b)
{
    if(a >= 0 && a < n && b >= 0 && b < n && s[a][b] != 'T' && s[a][b] != 'D' && s[a][b] != 'H') return true;
    return 0;
}
bool check_bear(ll a,ll b)
{
    if(a >= 0 && a < n && b >= 0 && b < n && s[a][b] != 'T' && s[a][b] != 'H' && mark[a][b] == 0) return true;
    return 0;
}
void bfs_hive(ll i,ll j)
{
    if(bee[i][j] == 0) return;
    memset(mark,false,sizeof mark);
    bee[i][j] = 0;
    mark[i][j] = 1;
    queue<pll> q;
    q.push({i,j});
    while(!q.empty())
    {
        pll u = q.front();
        q.pop();
        mark[u.fi][u.se] = 1;
        for(ll k = 0; k < 4; k++)
        {
            ll a = u.fi + row[k],b = u.se + col[k];
            if(check_bee(a,b) && bee[u.fi][u.se] + 1 < bee[a][b])
            {
                bee[a][b] = bee[u.fi][u.se] + 1;
                mark[a][b] = 1;
                q.push({a,b});
            }
        }
    }
}
void bfs(ll i,ll j )
{
    memset(mark,0,sizeof mark);
    mark[i][j] = 1;
    queue<pll> q;
    q.push({i,j});
    bear[i][j] = 0;
    while(!q.empty())
    {
        pll u = q.front();
        mark[u.fi][u.se] = 1;
        q.pop();
        for(ll k = 0; k < 4; k++)
        {
            ll a = u.fi + row[k],b = u.se + col[k];
            if(check_bear(a,b))
            {
                mark[a][b] = 1;
                bear[a][b] = bear[u.fi][u.se] + 1;
                q.push({a,b});
                //if(a == en.fi && b == en.se) return;
            }
        }
    }
}
bool f(ll x)
{
    memset(mark,0,sizeof mark);
    mark[start.fi][start.se] = 1;
    queue<pair<pll,ll>>q;
    q.push({start,0});
    while(!q.empty())
    {
        auto u = q.front();
        q.pop();
        mark[u.fi.fi][u.fi.se] = 1;
        for(ll i = 0; i < 4; i++)
        {
            ll a = u.fi.fi + row[i],b = u.fi.se + col[i];
            if(mark[a][b] == 0 && a >= 0 && a < n && b >= 0 && b < n && s[a][b] != 'T' && s[a][b] != 'H' && (x + ((u.se + 1) / step)) < bee[a][b])
            {
                mark[a][b] = 1;
                q.push({{a,b},u.se + 1});
            }
        }
    }
    if(mark[en.fi][en.se] == 1) return 1;
    return 0;
}
int main()
{
#define taskname "mecho"
    if (fopen(taskname".inp", "r"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> step;
    for(ll i = 0; i < n; i++)
    {
        cin >> s[i];
        for(ll j = 0; j < n; j++)
        {
            if(s[i][j] == 'M') start = {i,j};
            else if(s[i][j] == 'D') en = {i,j};
        }
    }
    memset(bee,60,sizeof bee);
    inf2 = bee[0][0];
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < n; j++) if(s[i][j] == 'H') bfs_hive(i,j);
    }
    bfs(start.fi,start.se);
    ll lf = 0,rt = inf - 1;
    while(lf <= rt)
    {
        ll mid = (lf + rt)/2;
        if(f(mid))
        {
            ans = mid;
            lf = mid + 1;
        }
        else rt = mid - 1;
    }
//    for(ll i = 0; i < n; i++)
//    {
//        for(ll j = 0; j < n; j++)
//        {
//            if(bee[i][j] != inf2) cout << bee[i][j] << ' ';
//            else cout << "-1 ";
//        }
//        cout << '\n';
//    }
//    for(ll i = 0; i < n; i++)
//    {
//        for(ll j = 0; j < n; j++)
//        {
//            if(bee[i][j] != inf2) cout << bear[i][j] << ' ';
//            else cout << "-1 ";
//        }
//        cout << '\n';
//    }
    if(ans == inf) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 84 / 100