Submission #1088865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088865		StefanSebez	Mecho (IOI09_mecho)	C++14	71 / 100	152 ms	7416 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int inf=1e9;
vector<string>a;
bool was[850][850];
int depth[850][850],dist[850][850],n,S;
bool Dobar(int x,int y){
	if(x<0||x>=n||y<0||y>=n||a[x][y]=='T'||was[x][y]) return false;
	return true;
}
int main(){
    scanf("%i%i",&n,&S);
    for(int i=0;i<n;i++){string s;cin>>s;a.pb(s);}
    int X0,Y0,X1,Y1;
    vector<pair<int,int> >H;
    for(int i=0;i<n;i++) for(int j=0;j<n;j++){if(a[i][j]=='M'){X0=i,Y0=j;}if(a[i][j]=='H')H.pb({i,j});if(a[i][j]=='D'){X1=i,Y1=j;}}
    queue<pair<int,int> >kju;
    for(auto i:H){kju.push(i);was[i.fi][i.se]=true;}
    while(kju.size()){
		int u=kju.front().fi,v=kju.front().se;kju.pop();
		if(Dobar(u-1,v)){depth[u-1][v]=depth[u][v]+1;was[u-1][v]=true;kju.push({u-1,v});}
		if(Dobar(u+1,v)){depth[u+1][v]=depth[u][v]+1;was[u+1][v]=true;kju.push({u+1,v});}
		if(Dobar(u,v-1)){depth[u][v-1]=depth[u][v]+1;was[u][v-1]=true;kju.push({u,v-1});}
		if(Dobar(u,v+1)){depth[u][v+1]=depth[u][v]+1;was[u][v+1]=true;kju.push({u,v+1});}
    }
    depth[X1][Y1]=inf;
    //for(int i=0;i<n;i++) {for(int j=0;j<n;j++) printf("%i ",depth[i][j]);printf("\n");}
    int l=0,r=5000,res=-1;
    while(l<=r){
		//printf("%i %i**\n",l,r);
		int mid=l+r>>1;
		for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) {dist[i][j]=0;was[i][j]=false;}
		if(depth[X0][Y0]>mid) kju.push({X0,Y0});was[X0][Y0]=true;
		bool moze=false;
		for(int i=S,dst=mid;kju.size();i+=S,dst++){
			while(kju.size()){
				int u=kju.front().fi,v=kju.front().se;
				//printf("%i %i\n",u,v);
				if(depth[u][v]<=dst){kju.pop();continue;}
				if(dist[u][v]>i) break;
				if(u==X1 && v==Y1) moze=true;
				if(dist[u][v]==i) break;
				kju.pop();
				if(Dobar(u-1,v)&&depth[u-1][v]>dst){dist[u-1][v]=dist[u][v]+1;was[u-1][v]=true;kju.push({u-1,v});}
				if(Dobar(u+1,v)&&depth[u+1][v]>dst){dist[u+1][v]=dist[u][v]+1;was[u+1][v]=true;kju.push({u+1,v});}
				if(Dobar(u,v-1)&&depth[u][v-1]>dst){dist[u][v-1]=dist[u][v]+1;was[u][v-1]=true;kju.push({u,v-1});}
				if(Dobar(u,v+1)&&depth[u][v+1]>dst){dist[u][v+1]=dist[u][v]+1;was[u][v+1]=true;kju.push({u,v+1});}
			}
		}
		if(moze) res=mid,l=mid+1;
		else r=mid-1;
    }
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int mid=l+r>>1;
      |           ~^~
mecho.cpp:38:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   38 |   if(depth[X0][Y0]>mid) kju.push({X0,Y0});was[X0][Y0]=true;
      |   ^~
mecho.cpp:38:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   38 |   if(depth[X0][Y0]>mid) kju.push({X0,Y0});was[X0][Y0]=true;
      |                                           ^~~
mecho.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%i%i",&n,&S);
      |     ~~~~~^~~~~~~~~~~~~~
mecho.cpp:38:18: warning: 'Y0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |   if(depth[X0][Y0]>mid) kju.push({X0,Y0});was[X0][Y0]=true;
      |      ~~~~~~~~~~~~^
mecho.cpp:38:18: warning: 'X0' may be used uninitialized in this function [-Wmaybe-uninitialized]
mecho.cpp:46:14: warning: 'Y1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     if(u==X1 && v==Y1) moze=true;
      |        ~~~~~~^~~~~~~~
mecho.cpp:46:5: warning: 'X1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     if(u==X1 && v==Y1) moze=true;
      |     ^~

• Subtask 1: 71 / 100