Submission #1267323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267323		mathduck	Mecho (IOI09_mecho)	C++20	17 / 100	448 ms	12316 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;
const long long inf = 1e18;
long long n,s,sx,sy,tx,ty,ans;
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] != 'T');
}
bool reach(long long bea,long long be){
	if (be<=0) return false;
	return (bea+s-1)/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,inf)),beartime(n+1,vector<long long>(n+1,inf));
    	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,beetime[u][v] = 0;
    	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;
    		}
    	}
    	if (beetime[sx][sy]>mid) q.emplace(sx,sy),bear[sx][sy] = 1,beartime[sx][sy] = 0;
    	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;
    		}
    	}
    	if (bear[tx][ty] && reach(beartime[tx][ty], beetime[tx][ty] - mid)) 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: 17 / 100