Submission #124675

#	Time	Username	Problem	Language	Result	Execution time	Memory
124675		arthurconmy	Mecho (IOI09_mecho)	C++14	6 / 100	1081 ms	13264 KiB

mecho

// check ctrl+v :^)
/* Arthur Conmy IOI template - minimal! */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int,int>;
#define ff first
#define ss second
#define pb push_back
#define REP(i,a,b) \
for(int i = int(a); i<=int(b); i++)

int grid[802][802]; // 0: tree / boundary
					// 1: grass 
					// 2: hive
					// 3: mecho's home

int bee_dis[802][802];
int INF = int(1e9);
pii start;
int n,s;
bool vis[802][802];

bool try_it(int t)
{
	vector<pii> BFS = {start};

	int cur_dis=0;

	while(!BFS.empty())
	{
		// cout << cur_dis << endl;

		if(cur_dis%s == 0 && cur_dis!=0) t++;

		vector<pii> new_BFS;

		for(auto P:BFS)
		{
			REP(x,-1,1)
			{
				REP(y,-1,1)
				{
					// cout << P.ff+x << " " << P.ff+y << endl;

					if(vis[P.ff+x][P.ss+y]) continue;
					if(abs(x)+abs(y)!=1) continue;
					if(bee_dis[P.ff+x][P.ss+y] <= t) continue; // do we need to check that the current square isn't now bad?
						
					if(grid[P.ff+x][P.ss+y] == 3) return true;

					if(grid[P.ff+x][P.ss+y] != 1) continue;

					new_BFS.pb({P.ff+x,P.ss+y});
					vis[P.ff+x][P.ss+y]=1;
				}
			}

			BFS=new_BFS;
		}

		cur_dis++;
	}

	return false;
}

int main()
{
	#ifdef ARTHUR_LOCAL
		ifstream cin("input.txt");
	#endif

	REP(i,0,801)
	{
		REP(j,0,801)
		{
			bee_dis[i][j]=INF;
		}
	}

	cin>>n>>s;

	vector<pii> bees;

	REP(i,1,n)
	{
		string row;
		cin>>row;

		REP(j,1,n)
		{
			if(row[j-1]=='G') grid[i][j]=1;
			if(row[j-1]=='H')
			{
				grid[i][j]=2;
				bees.pb({i,j});
				bee_dis[i][j]=0;
			}
			if(row[j-1]=='M')
			{
				grid[i][j]=1; // Mecho's start is grassy
				start={i,j};
			}
			if(row[j-1]=='D')
			{
				grid[i][j]=3;
			}
		}
	}

	// precompute bee_dis

	while(!bees.empty())
	{
		vector<pii> new_bees;

		for(auto b:bees)
		{
			REP(x,-1,1)
			{
				REP(y,-1,1)
				{
					if(abs(x)+abs(y)!=1) continue;
					if(bee_dis[b.ff+x][b.ss+y] != INF) continue;
					if(grid[b.ff+x][b.ss+y] != 1) continue;

					bee_dis[b.ff+x][b.ss+y]=1+bee_dis[b.ff][b.ss];
					new_bees.pb({b.ff+x,b.ss+y});
				}
			}
		}

		bees=new_bees;
	}

	// REP(i,1,n)
	// {
	// 	REP(j,1,n)
	// 	{
	// 		if(bee_dis[i][j]==INF)
	// 		{
	// 			cout << "-1 ";
	// 			continue;
	// 		}

	// 		cout << bee_dis[i][j] << " ";
	// 		if(bee_dis[i][j]<10) cout << " "; 
	// 	}
	// 	cout << endl;
	// }

	vis[start.ff][start.ss]=1;
	int l=0;
	int r=n*n; // bin search parameters

	while(l<r)
	{
		REP(i,0,801)
		{
			REP(j,0,801)
			{
				vis[i][j]=0;
			}
		}

		// cout << l << " " << r << endl;

		vis[start.ff][start.ss]=1;

		int mid=(l+r)/2;

		if(try_it(mid))
		{
			l=mid;
		}

		else
		{
			r=mid-1;
		}
	}

	REP(i,0,801)
	{
		REP(j,0,801)
		{
			vis[i][j]=0;
		}
	}

	if(!try_it(0)) cout << -1 << endl;
	else cout << l << endl;
}

• Subtask 1: 6 / 100