Submission #151332

#	Time	Username	Problem	Language	Result	Execution time	Memory
151332		GioChkhaidze	Mecho (IOI09_mecho)	C++14	100 / 100	293 ms	7040 KiB

mecho

#include <bits/stdc++.h> 
#define F first
#define S second
using namespace std;
const int N=805;
int n,ANS=-1,k,Timer[N][N],F[N][N];
char c[N][N];
pair < int , int > a[6],Home,Honeypot;
vector < pair < int , int > > Hive;
void Bfs () {
	queue < pair < int , int > > q;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			Timer[i][j]=1e9;
	
	for (int i=0; i<Hive.size(); i++) 
		q.push(Hive[i]),Timer[Hive[i].F][Hive[i].S]=0;
	
	while (!q.empty()) {
		pair < int , int > B=q.front();
		q.pop();
		for (int i=1; i<=4; i++) {
			int X=B.F+a[i].F,Y=B.S+a[i].S;
			if (!(1<=X && X<=n && 1<=Y && Y<=n)) continue;
			if (c[X][Y]=='T' || c[X][Y]=='D' || Timer[X][Y]!=1e9) continue;	
			Timer[X][Y]=Timer[B.F][B.S]+k;
			q.push({X,Y});
		}
	}
}

bool check(int x) {
	if (x*k>=Timer[Honeypot.F][Honeypot.S]) return 0;
	queue < pair < pair < int , int > , int > > Q;
	while (!Q.empty()) Q.pop();
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
			F[i][j]=0;

	Q.push({{Honeypot.F,Honeypot.S},(x*k)});
	F[Honeypot.F][Honeypot.S]=1;

	while (!Q.empty()) {
		pair < int , int > D=Q.front().F;
		int timer=Q.front().S;
		Q.pop();
		if (c[D.F][D.S]=='D') return 1;
		for (int i=1; i<=4; i++) {
			int X=D.F+a[i].F,Y=D.S+a[i].S;
			if (!(1<=X && X<=n && 1<=Y && Y<=n)) continue;
			if (Timer[X][Y]<=timer+1 || F[X][Y] || c[X][Y]=='T') continue;
			Q.push({{X,Y},timer+1});
			F[X][Y]=1;
		}	
	}
	return 0;
}

main () { 
	a[1].F=1; a[1].S=0;
	a[2].F=-1; a[2].S=0;
	a[3].F=0; a[3].S=1;
	a[4].F=0; a[4].S=-1;
	
	cin>>n>>k;
	
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++){
			cin>>c[i][j];
			if (c[i][j]=='M') Honeypot.F=i,Honeypot.S=j;
			if (c[i][j]=='H') Hive.push_back({i,j});
			if (c[i][j]=='D') Home.F=i,Home.S=j;	
		}
	Bfs();
	int l=0,r=n*n,mid=0;
	while (l<=r) {
		mid=(l+r)/2;
		if (check(mid)) { ANS=mid; l=mid+1; }
			else r=mid-1;
	}
	cout<<ANS<<endl;
}

Compilation message (stderr)

mecho.cpp: In function 'void Bfs()':
mecho.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<Hive.size(); i++) 
                ~^~~~~~~~~~~~
mecho.cpp: At global scope:
mecho.cpp:59:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () { 
       ^

• Subtask 1: 100 / 100