Submission #1265217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265217		Duelist1234	Mecho (IOI09_mecho)	C++20	0 / 100	31 ms	9032 KiB

mecho

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include <utility>
#include <map>
#define ll long long int
const ll mod=1e9+7;
using namespace std;
/*
? Did I test edge cases? (Empty, min/max, 1-element, same elements, etc.)
? Did I reread the full prompt to recheck constraints?
? Does my code handle ties, negatives, zeroes, or duplicates?
? Am I brute-forcing something unnecessarily?
? Am I assuming things not in the problem?

Have I defined all state variables explicitly?
Do I know what each transition costs?
Have I written 2 edge-case scenarios by hand?
*/
queue<pair<int,int> > prep;
queue<int> clos;
int closest[800][800];
int d;
int n;
void bfs1(int i,int j,int visited2[][800],int c,int n,string a[])
{
	prep.pop();
	clos.pop();
	if(a[i][j]=='H')
	closest[i][j]=0;
	else
	closest[i][j]=c;
	if(i!=0)
	if(visited2[i-1][j]!=1 and a[i-1][j]!='T')
	{
		visited2[i-1][j]=1;
		prep.push(make_pair(i-1,j));
		clos.push(c+1);
	}
	if(i!=n-1)
    if(visited2[i+1][j]!=1 and a[i+1][j]!='T')
	{
		visited2[i+1][j]=1;
		prep.push(make_pair(i+1,j));
		clos.push(c+1);
	}
	if(j!=0)
	if(visited2[i][j-1]!=1 and a[i][j-1]!='T')
	{
		visited2[i][j-1]=1;
		prep.push(make_pair(i,j-1));
		clos.push(c+1);
	}
	if(j!=n-1)
    if(visited2[i][j+1]!=1 and a[i][j+1]!='T')
	{
		visited2[i][j+1]=1;
		prep.push(make_pair(i,j+1));
		clos.push(c+1);
	}
	if(prep.size())
	bfs1(prep.front().first,prep.front().second,visited2,clos.front(),n,a);
}
int r(int steps,int d)
{
	if(steps%d)
	return steps/d+1;
	else
	return steps/d;
}
/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT*/
int bfs(string a[],int visited[][800],int i,int j,queue<int>& time,queue<pair<int,int> >& order,int ext)
{
	order.pop();
	if(a[i][j]=='D')
	{
		return 1;
	}
	if(ext+r(time.front(),d)>=closest[i][j] or a[i][j]=='H' or a[i][j]=='T')
	{
		if(order.size())
		return bfs(a,visited,order.front().first,order.front().second,time,order,ext);
		return 0;
	}
	if(i!=n-1)
	if(visited[i+1][j]!=1 and a[i+1][j]!='T')
	{
		visited[i+1][j]=1;
		time.push(time.front()+1);
		order.push(make_pair(i+1,j));
	}
	if(i!=0)
	if(visited[i-1][j]!=1 and a[i-1][j]!='T')
	{
		visited[i-1][j]=1;
		time.push(time.front()+1);
		order.push(make_pair(i-1,j));
	}
	if(j!=n-1)
	if(visited[i][j+1]!=1 and a[i][j+1]!='T')
	{
		visited[i][j+1]=1;
		time.push(time.front()+1);
		order.push(make_pair(i,j+1));
	}
	if(j!=0)
	if(visited[i][j-1]!=1 and a[i][j-1]!='T')
	{
		visited[i][j-1]=1;
		time.push(time.front()+1);
		order.push(make_pair(i,j-1));
	}
	time.pop();
	if(time.size())
	return bfs(a,visited,order.front().first,order.front().second,time,order,ext);
	return 0;
}
int main(){
	//cin.tie(0)->sync_with_stdio(false);
	cin>>n>>d;
	string a[n];
	int visited2[800][800],start1,start2;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		for(int j=0;j<n;j++)
		{
			if(a[i][j]=='H')
			{
				prep.push(make_pair(i,j));
				clos.push(0);
				visited2[i][j]=1;
			}
			else if(a[i][j]=='M')
			{
				start1=i;
				start2=j;
			}
		}
	}
	bfs1(prep.front().first,prep.front().second,visited2,0,n,a);
	int l=0,r=n*n,ans=-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		queue<pair<int,int> > order;
		order.push(make_pair(start1,start2));
		int visited[800][800];
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		visited[i][j]=0;
		queue<int> time;
		while(time.size())
		time.pop();
		while(order.size())
		order.pop();
		time.push(0);
		if(bfs(a,visited,start1,start2,time,order,mid))
		{
			//ans=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}

	

• Subtask 1: 0 / 100