Submission #468616

#	Time	Username	Problem	Language	Result	Execution time	Memory
468616		Yuisuyuno	Mecho (IOI09_mecho)	C++14	84 / 100	228 ms	11616 KiB

mecho

//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 805
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
const int minf = -1e10;

int n, s;
char a[N][N];
ii M, D;
vector<ii> bee;

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        //freopen(Task".out","w",stdout);
    }
    cin >> n >> s;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
            if (a[i][j]=='M') M = ii(i,j);
            if (a[i][j]=='D') D = ii(i,j);
            if (a[i][j]=='H') bee.pb(ii(i,j));
        }
    }
}

int d[N][N];
int dm[N][N];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
bool ok(int x, int y){
    if (1 <= x && x <= n && 1 <= y && y <= n) return true;
    return false;
}

void build_bee(){
    queue<ii> q;
    memset(d, -1, sizeof d);
    for(ii x : bee){
        d[x.fi][x.se]=0;
        q.push(ii(x.fi,x.se));
    }
    while (q.size()){
        int u = q.front().fi;
        int v = q.front().se;
        //cout << u << ' ' << v << ' ' << d[u][v] << endl;
        q.pop();
        for(int i=0; i<4; i++){
            int x = u + dx[i];
            int y = v + dy[i];
            if (d[x][y]==-1 && ok(x,y) && (a[x][y]=='G'||a[x][y]=='M')){
                d[x][y] = d[u][v] +1;
                q.push(ii(x,y));
            }
        }
    }
}

bool can_eat(int ti){
    queue<ii> q;
    memset(dm, -1, sizeof dm);
    dm[M.fi][M.se] = 0;
    q.push(ii(M.fi,M.se));
    while (q.size()){
        int u = q.front().fi;
        int v = q.front().se;
        q.pop();
        for(int i=0; i<4; i++){
            int x = u + dx[i];
            int y = v + dy[i];
            if (!ok(x,y) || a[x][y]=='T' || a[x][y]=='H') continue;
            if (x==D.fi && y==D.se) return true;
            if (dm[x][y]==-1){
                dm[x][y] = dm[u][v] + 1;
                if (dm[x][y]/s + ti < d[x][y]){
                    q.push(ii(x,y));
                }
            }
        }
    }
    return false;
}

void proc()
{
    build_bee();
    int l = 0, r = 1e9, ans=-1;
    while (r-l > 0){
        int mid = (l+r)/2;
        if (can_eat(mid)){
            l = mid+1;
            ans = mid;
        }
        else r = mid;
    }
    cout << ans;
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'void readfile()':
mecho.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 84 / 100