Submission #754291

#	Time	Username	Problem	Language	Result	Execution time	Memory
754291		TimDee	Mecho (IOI09_mecho)	C++17	100 / 100	415 ms	17292 KiB

mecho

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];

const int inf=1e18;

const int N=800;
string a[N];
int d[N][N];
int p[N][N];
int vis[N][N];

void clear(int n) {
	forn(i,n) forn(j,n) d[i][j]=0;
}
void reset(int n) {
	forn(i,n) forn(j,n) vis[i][j]=0;
}

struct z {
	int f,s,d,d1,d2;
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {

	int n,s; cin>>n>>s;
	forn(i,n) cin>>a[i];

	forn(i,n) forn(j,n) p[i][j]=inf;
	queue<z> q;
	forn(i,n) forn(j,n) if (a[i][j]=='H') {
		q.push({i,j,0});
	}

	while (q.size()) {
		auto it=q.front(); q.pop();
		int x=it.f, y=it.s, d=it.d;
		if (x<0 || y<0) continue;
		if (x>=n || y>=n) continue;
		if (vis[x][y]) continue;
		if (a[x][y]=='T' || a[x][y]=='D') continue;
		vis[x][y]=1;
		p[x][y]=d;
		q.push({x-1,y,d+1});
		q.push({x+1,y,d+1});
		q.push({x,y-1,d+1});
		q.push({x,y+1,d+1});
	}

	int l=-1, r=1e9;
	pi D;
	forn(i,n) forn(j,n) if (a[i][j]=='D') D={i,j};
	while (l<r) {
		int mid=(l+r+1)>>1;
		reset(n);
		forn(i,n) forn(j,n) if (a[i][j]=='M') {
			q.push({i,j,0,0,0});
		}

		while (q.size()) {
			auto it=q.front(); q.pop();
			int x=it.f, y=it.s, d=it.d, d1=it.d1, d2=it.d2;
			//cout<<mid<<": "<<x<<' '<<y<<' '<<d<<' '<<vis[x][y]<<' '<<p[x][y]<<' '<<a[x][y]<<'\n';
			if (x<0 || y<0) continue;
			if (x>=n || y>=n) continue;
			if (vis[x][y]) continue;
			if (a[x][y]=='T') continue;
			if (p[x][y]<mid+(d+s-1)/s) continue;
			if (p[x][y]==mid+(d+s-1)/s) {
				if (d%s) {

				} else {
					continue;
				}
			}
			vis[x][y]=1;
			q.push({x-1,y,d+1});
			q.push({x+1,y,d+1});
			q.push({x,y-1,d+1});
			q.push({x,y+1,d+1});
		}
		if (vis[D.f][D.s]) l=mid;
		else r=mid-1;
	}
	cout<<r<<'\n';

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
}

Compilation message (stderr)

mecho.cpp: In function 'void solve()':
mecho.cpp:72:32: warning: unused variable 'd1' [-Wunused-variable]
   72 |    int x=it.f, y=it.s, d=it.d, d1=it.d1, d2=it.d2;
      |                                ^~
mecho.cpp:72:42: warning: unused variable 'd2' [-Wunused-variable]
   72 |    int x=it.f, y=it.s, d=it.d, d1=it.d1, d2=it.d2;
      |                                          ^~

• Subtask 1: 100 / 100