Submission #408684

#	Time	Username	Problem	Language	Result	Execution time	Memory
408684		Jasiekstrz	Mecho (IOI09_mecho)	C++17	84 / 100	442 ms	9540 KiB

mecho

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF=1e9+7;
const int N=800;
struct Pos
{
	int x,y;
	Pos(int _x=0,int _y=0) : x(_x), y(_y) {};
	bool operator==(const Pos &oth)
	{
		return (x==oth.x && y==oth.y);
	}
	vector<Pos> edges()
	{
		vector<Pos> tmp;
		tmp.reserve(4);
		for(auto dd:{make_pair(0,-1),make_pair(0,1),make_pair(-1,0),make_pair(1,0)})
			tmp.push_back({x+dd.fi,y+dd.se});
		return tmp;
	}
};
bool fr[N+10][N+10];
queue<Pos> qq;
int bt[N+10][N+10];
pair<int,int> d[N+10][N+10];
bool ok(Pos start,Pos finish,int s,int time,int n)
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			d[i][j]={INF,INF};
	}
	d[start.x][start.y]={time,0};
	qq.push(start);
	while(!qq.empty())
	{
		auto x=qq.front();
		qq.pop();
		vector<Pos> e=x.edges();
		pair<int,int> tn=(d[x.x][x.y].se+1>=s ? make_pair(d[x.x][x.y].fi+1,0):
				make_pair(d[x.x][x.y].fi,d[x.x][x.y].se+1));
		for(auto v:e)
		{
			if((fr[v.x][v.y] || v==finish) && d[v.x][v.y].se==INF && bt[v.x][v.y]>tn.fi)
			{
				d[v.x][v.y]=tn;
				qq.push(v);
			}
		}
	}
	return (d[finish.x][finish.y].fi!=INF);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,s;
	Pos start,finish;
	cin>>n>>s;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			bt[i][j]=INF;
			char c;
			cin>>c;
			if(c=='T')
			{
				fr[i][j]=false;
			}
			else if(c=='G')
			{
				fr[i][j]=true;
			}
			else if(c=='M')
			{
				fr[i][j]=true;
				start=Pos(i,j);
			}
			else if(c=='D')
			{
				fr[i][j]=false;
				finish=Pos(i,j);
			}
			else if(c=='H')
			{
				fr[i][j]=false;
				qq.push(Pos(i,j));
				bt[i][j]=0;
			}
		}
	}
	while(!qq.empty())
	{
		Pos a=qq.front();
		qq.pop();
		vector<Pos> e=a.edges();
		for(auto v:e)
		{
			if(fr[v.x][v.y] && bt[v.x][v.y]==INF)
			{
				bt[v.x][v.y]=bt[a.x][a.y]+1;
				qq.push(v);
			}
		}
	}
	//for(int i=1;i<=n;i++)
	//{
	//	for(int j=1;j<=n;j++)
	//		cerr<<bt[i][j]<<" ";
	//	cerr<<"\n";
	//}
	if(!ok(start,finish,s,0,n))
	{
		cout<<"-1\n";
		return 0;
	}
	int bg=0,en=INF;
	while(bg<en)
	{
		int mid=(bg+en+1)/2;
		if(ok(start,finish,s,mid,n))
			bg=mid;
		else
			en=mid-1;
	}
	cout<<bg<<"\n";
	return 0;
}

• Subtask 1: 84 / 100