Submission #1267327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267327		mathduck	Mecho (IOI09_mecho)	C++20	100 / 100	452 ms	12312 KiB

mecho

//Author : Mathduck :P
//VOI this year
//Drink coffee and see me code
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define __Mathduck__ signed main()
#include <bits/stdc++.h>
using namespace std;
const long long maxn =1e3+177;
long long n,s,sx,sy,tx,ty,ans=-1;
long long dx[] = {-1, 0, 1, 0};
long long dy[] = {0, -1, 0, 1};
char a[maxn][maxn];
vector<pair<long long,long long>> hive;
bool inside(long long u,long long v){
	return (u>=1 && u<=n && v>=1 && v<=n && (a[u][v]=='G' || a[u][v] =='M'));
}
bool reach(long long bea,long long be){
	return bea/s < be;
}
__Mathduck__{
    //freopen("input.inp","r",stdin);freopen("output.out","w",stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>s;
    for (int i = 1;i<=n;i++) for (int j = 1;j<=n;j++)cin>>a[i][j];
    for (int i = 1;i<=n;i++) for (int j = 1;j<=n;j++){
    	if (a[i][j] == 'M') sx = i,sy = j;
    	else if (a[i][j] == 'H') hive.emplace_back(i,j);
    	else if (a[i][j] == 'D') tx =i,ty = j;
    }
    long long l = 0,r = n*n;
    while(l<=r){
    	vector<vector<bool>> bee(n+1,vector<bool>(n+1,false)),bear(n+1,vector<bool>(n+1,false));
    	vector<vector<long long>> beetime(n+1,vector<long long>(n+1,0)),beartime(n+1,vector<long long>(n+1,0));
    	queue<pair<long long,long long>> q;
    	long long mid = l+r >> 1;
    	for (auto [u,v]:hive) q.emplace(u,v),bee[u][v] = true;
    	while(!q.empty()){
    		auto [u,v] = q.front();q.pop();
    		for (int i = 0;i<4;i++){
    			long long nx = u+dx[i],ny = v+dy[i];
    			if (inside(nx,ny) && !bee[nx][ny]) beetime[nx][ny] = beetime[u][v]+1,q.emplace(nx,ny),bee[nx][ny] = true;
    		}
    	}
    	q.emplace(sx,sy);
    	bear[sx][sy] = true;
    	if (beetime[sx][sy]<=mid) q.pop();
    	while(!q.empty()){
    		auto [u,v] = q.front();q.pop();
    		for (int i = 0;i<4;i++){
    			long long nx = u+dx[i],ny = v+dy[i];
    			if (inside(nx,ny) && !bear[nx][ny] && reach(beartime[u][v]+1,beetime[nx][ny]-mid)) bear[nx][ny] = true,q.emplace(nx,ny),beartime[nx][ny] = beartime[u][v] +1;
    		}
    	}
    	bool check =false;
    	for (int i = 0;i<4;i++){
    		long long nx = tx+dx[i],ny =ty+dy[i];
    		if (inside(nx,ny) && reach(beartime[nx][ny],beetime[nx][ny]-mid) && bear[nx][ny]){
    			check = true;
    			break;
    		}
    	}
    	if (check) ans = mid,l = mid+1;
    	else r = mid-1;
    }
    cout<<ans;
    cerr << "Time elapsed: " << TIME << " s.\n";
}
/*
INPUT :

OUTPUT :

If it WA, check :
- Special case (Usually, n=1)
- WRONG FORMAT OUTPUT
- Check reading
- Change (ll) to (ull)
- lleger Overflow (The number that bigger than 2^63-1)
- trick lỏ #pragma GCC optimize("O2")
           #pragma GCC target("avx,avx2,fma")
*/
// check time:cerr << "Time elapsed: " << TIME << " s.\n";

• Subtask 1: 100 / 100