Submission #1121203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121203		sktodow	Mecho (IOI09_mecho)	C++17	100 / 100	512 ms	12088 KiB

mecho

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#define int long long int
#define pb push_back
#define mid (l+(r-l)/2)
#define f first
#define s second
static const int N=800;
static const int MOD=(1LL<<61)-1;
static const int inf=INT64_MAX;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
 
void io(string name = ""){ 
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}

vector<string>v(N);
int n,s;

bool inside(int x, int y) {return x>=0 && x<n && y>=0 && y<n &&(v[x][y]=='G' || v[x][y]=='M');}

bool check(int i,int j){ return i/s < j;}

int32_t main() {
	//io("local");
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin>>n>>s;
	for(int i=0;i<n;i++){cin>>v[i];}

	vector<array<int,2>>h;
	int mx, my, hx, hy;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(v[i][j]=='M'){mx=i,my=j;}
			else if(v[i][j]=='H'){h.pb({i,j});}
			else if(v[i][j]=='D'){hx=i,hy=j;}
		}
	}

	int dx[]={-1, 0, 1, 0};
	int dy[]={0, -1, 0, 1};

	int l=0,r=n*n;
	while (l<=r) {
		vector<vector<int>>bee(n,vector<int>(n));
		vector<vector<int>>mecho(n,vector<int>(n));
		vector<vector<bool>>visB(n,vector<bool>(n));
		vector<vector<bool>>visM(n,vector<bool>(n));
		queue<array<int,2>>q;

		for (auto i:h) {
			q.push({i[0], i[1]});
			visB[i[0]][i[1]]=1;
		}

		while (!q.empty()) {
			int x=q.front()[0],y=q.front()[1];
			q.pop();
			for(int i=0;i<4;i++){
				int cx=x+dx[i],cy=y+dy[i];
				if(inside(cx,cy)&&!visB[cx][cy]){
					bee[cx][cy]=bee[x][y]+1;
					q.push({cx,cy});
					visB[cx][cy]=1;
				}
			}
		}

		q.push({mx,my});
		visM[mx][my]=1;
		if (bee[mx][my]<=mid){q.pop();}

		while (!q.empty()) {
			int x=q.front()[0],y=q.front()[1];
			q.pop();
			for(int i=0;i<4;i++){
				int cx=x+dx[i],cy=y+dy[i];
				if (inside(cx,cy) && !visM[cx][cy] && check(mecho[x][y]+1,bee[cx][cy]-mid)){
					visM[cx][cy]=1;
					q.push({cx,cy});
					mecho[cx][cy]=mecho[x][y]+1;
				}
			}
		}

		bool chc=false;
		for(int i=0;i<4;i++){
			int cx=hx+dx[i],cy=hy+dy[i];
			if(inside(cx,cy) && check(mecho[cx][cy],bee[cx][cy]-mid) && visM[cx][cy]){chc=1;}
		}
		if(chc){l=mid+1;}
		else{r=mid-1;}
	}
	cout<<l-1;
}

Compilation message (stderr)

mecho.cpp: In function 'void io(std::string)':
mecho.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp: In function 'int32_t main()':
mecho.cpp:94:20: warning: 'hy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |    int cx=hx+dx[i],cy=hy+dy[i];
      |                    ^~
mecho.cpp:94:8: warning: 'hx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   94 |    int cx=hx+dx[i],cy=hy+dy[i];
      |        ^~
mecho.cpp:76:10: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |   visM[mx][my]=1;
      |          ^

• Subtask 1: 100 / 100