Submission #499813

#	Time	Username	Problem	Language	Result	Execution time	Memory
499813		Hi_Im_Not_Meo_Meo	Mecho (IOI09_mecho)	C++14	84 / 100	203 ms	6884 KiB

mecho

#include"bits/stdc++.h"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define fi first
#define se second
#define mp make_pair

const int N = 808;
const int oo = 2e9;
const int C[] = {0,1,0,-1,0};
using namespace std;
using pii = pair<int,int>;
int n, s;
int f[N][N], cx[N][N];
char a[N][N];
pii st, ed;

struct dota{
	int x, y, tim;
};

bool check(int t){
    queue<dota> q;
    memset(cx,0,sizeof(cx));
    f(i,1,n) f(j,1,n) if(a[i][j] != 'T') cx[i][j] = 1;
    q.push({st.fi,st.se,0});
    cx[st.fi][st.se] = 0;
    while(q.size()){
        dota td = q.front(); q.pop();
        int x = td.x;
        int y = td.y;
        int tim = td.tim;
        //if(t == 1) cout<<x<<" "<<y<<" "<<tim<<endl;
        if(x == ed.fi && y == ed.se) return true;
        f(i,0,3){
        	int u = x + C[i];
        	int v = y + C[i+1];
            if(cx[u][v] && (tim + 1)/s < f[u][v]-t){
             	q.push({u,v,tim+1});
             	cx[u][v] = 0;
        	}
        }
        
    }
    return false;
}

main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>s;
	f(i,1,n) f(j,1,n) cin>>a[i][j];
	queue<pii> q;
	memset(cx,0,sizeof(cx));
	f(i,0,n) cx[i][0] = cx[0][i] = cx[i][n+1] = cx[n+1][i] = 1; 
	f(i,1,n) f(j,1,n){
		if(a[i][j] == 'T') cx[i][j] = 1;
		if(a[i][j] == 'H'){
			cx[i][j] = 1;
		 	q.push({i,j});
		 	f[i][j] = 0;
		}
		if(a[i][j] == 'D') ed = mp(i,j);
		if(a[i][j] == 'M') st = mp(i,j);
	}
	while(q.size()){
		pii td = q.front(); q.pop();
		int x = td.fi, y = td.se;
		f(i,0,3){
			int u = x + C[i];
			int v = y + C[i+1];
			if(!cx[u][v]){
				f[u][v] = f[x][y]+1;
				cx[u][v] = true;
				q.push({u,v});
			}
		}
	}
	
	f[ed.fi][ed.se] = oo;
	//f(i,1,n){
	//	f(j,1,n) cout<<f[i][j]<<" ";
	//	cout<<endl;
	//}
	int l = 0, r = oo, mid, ans = -1;
	while(l <= r){
		mid = (l+r)/2;
		if(check(mid)) ans = mid,l = mid+1;
		else r = mid-1;
	}
	cout<<ans;
}

Compilation message (stderr)

mecho.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

• Subtask 1: 84 / 100