제출 #790757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790757		Gray	Mecho (IOI09_mecho)	C++17	21 / 100	1091 ms	6836 KiB

mecho

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define ln "\n"
#define ff first
#define ss second
#define INF 2e9
using namespace std;

void solve(){
	ll n, s; cin >> n >> s;
	vector<vector<char>> gr(n, vector<char>(n));
	vector<pair<ll, ll>> hvs;
	pair<ll, ll> bcor, hcor;
	for (ll i=0; i<n; i++){
		for (ll j=0; j<n; j++){
			cin >> gr[i][j];
			if (gr[i][j]=='H'){
				hvs.push_back({i, j});
			}else if (gr[i][j]=='M'){
				bcor = {i, j};
			}else if (gr[i][j]=='D'){
				hcor = {i, j};
			}
		}
	}
	vector<vector<ll>> hpath(n, vector<ll>(n, INF));

	auto bfs1 = [&](pair<ll, ll> cord){
		hpath[cord.ff][cord.ss]=1;
		vector<vector<ll>> vi(n, vector<ll>(n, INF));
		queue<pair<ll, ll>> q;
		q.push(cord);
		vi[cord.ff][cord.ss]=1;
		while (!q.empty()){
			pair<ll, ll> cur = q.front();
			q.pop();
			if (cur.ff>0 and vi[cur.ff-1][cur.ss]==INF and gr[cur.ff-1][cur.ss]!='T' and gr[cur.ff-1][cur.ss]!='D' and gr[cur.ff-1][cur.ss]!='H'){
				vi[cur.ff-1][cur.ss]=vi[cur.ff][cur.ss]+1;
				hpath[cur.ff-1][cur.ss]=min(hpath[cur.ff-1][cur.ss], vi[cur.ff-1][cur.ss]);
				q.push({cur.ff-1, cur.ss});
			}
			if (cur.ss>0 and vi[cur.ff][cur.ss-1]==INF and gr[cur.ff][cur.ss-1]!='T' and gr[cur.ff][cur.ss-1]!='D' and gr[cur.ff][cur.ss-1]!='H'){
				vi[cur.ff][cur.ss-1]=vi[cur.ff][cur.ss]+1;
				hpath[cur.ff][cur.ss-1]=min(hpath[cur.ff][cur.ss-1], vi[cur.ff][cur.ss-1]);
				q.push({cur.ff, cur.ss-1});
			}
			if (cur.ff+1<n and vi[cur.ff+1][cur.ss]==INF and gr[cur.ff+1][cur.ss]!='T' and gr[cur.ff+1][cur.ss]!='D' and gr[cur.ff+1][cur.ss]!='H'){
				vi[cur.ff+1][cur.ss]=vi[cur.ff][cur.ss]+1;
				hpath[cur.ff+1][cur.ss]=min(hpath[cur.ff+1][cur.ss], vi[cur.ff+1][cur.ss]);
				q.push({cur.ff+1, cur.ss});
			}
			if (cur.ss+1<n and vi[cur.ff][cur.ss+1]==INF and gr[cur.ff][cur.ss+1]!='T' and gr[cur.ff][cur.ss+1]!='D' and gr[cur.ff][cur.ss+1]!='H'){
				vi[cur.ff][cur.ss+1]=vi[cur.ff][cur.ss]+1;
				hpath[cur.ff][cur.ss+1]=min(hpath[cur.ff][cur.ss+1], vi[cur.ff][cur.ss+1]);
				q.push({cur.ff, cur.ss+1});
			}
		}
	};
	auto bfs2 = [&](ll wt) -> bool{
		pair<ll, ll> cord = bcor;
		if (hpath[cord.ff][cord.ss]-1<wt) {
			// cout << "Fail at start: " << hpath[cord.ff][cord.ss] << " <: " << cord.ff << "," << cord.ss << " -> " << wt << ln; 
			return 0;
		}
		vector<vector<ll>> vi(n, vector<ll>(n, INF));
		queue<pair<ll, ll>> q;
		q.push(cord);
		vi[cord.ff][cord.ss]=wt;
		while (!q.empty()){
			pair<ll, ll> cur = q.front();
			q.pop();
			// cout << "(" << cur.ss << "," << cur.ff << ") -> hpath=" << hpath[cur.ff][cur.ss] << "; mdist=" << vi[cur.ff][cur.ss]-wt << "; required=" << ((vi[cur.ff][cur.ss]-wt)/s+wt) << "; " << " possible=" << hpath[cur.ff][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1 << ln;
			if (cur.ff>0 and vi[cur.ff-1][cur.ss]==INF and gr[cur.ff-1][cur.ss]!='T' and gr[cur.ff-1][cur.ss]!='H' and ((vi[cur.ff][cur.ss]-wt)/s+wt)<=(hpath[cur.ff-1][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1)){
				// cout << (hpath[cur.ff-1][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to U: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln;
				vi[cur.ff-1][cur.ss]=vi[cur.ff][cur.ss]+1;
				q.push({cur.ff-1, cur.ss});
			}
			if (cur.ss>0 and vi[cur.ff][cur.ss-1]==INF and gr[cur.ff][cur.ss-1]!='T' and gr[cur.ff][cur.ss-1]!='H' and ((vi[cur.ff][cur.ss]-wt)/s+wt)<=(hpath[cur.ff][cur.ss-1]-(vi[cur.ff][cur.ss]-wt)/s-1)){
				// cout << (hpath[cur.ff][cur.ss-1]-(vi[cur.ff][cur.ss]-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to L: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln;
				vi[cur.ff][cur.ss-1]=vi[cur.ff][cur.ss]+1;
				q.push({cur.ff, cur.ss-1});
			}
			if (cur.ff+1<n and vi[cur.ff+1][cur.ss]==INF and gr[cur.ff+1][cur.ss]!='T' and gr[cur.ff+1][cur.ss]!='H' and ((vi[cur.ff][cur.ss]-wt)/s+wt)<=(hpath[cur.ff+1][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1)){
				// cout << (hpath[cur.ff+1][cur.ss]-(vi[cur.ff][cur.ss]-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to D: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln;
				vi[cur.ff+1][cur.ss]=vi[cur.ff][cur.ss]+1;
				q.push({cur.ff+1, cur.ss});
			}
			if (cur.ss+1<n and vi[cur.ff][cur.ss+1]==INF and gr[cur.ff][cur.ss+1]!='T' and gr[cur.ff][cur.ss+1]!='H' and ((vi[cur.ff][cur.ss]-wt)/s+wt)<=(hpath[cur.ff][cur.ss+1]-(vi[cur.ff][cur.ss]-wt)/s-1)){
				// cout << (hpath[cur.ff][cur.ss+1]-(vi[cur.ff][cur.ss]+1-wt)/s-1) << " <- " << cur.ss << "," << cur.ff << " to R: cmx " << vi[cur.ff][cur.ss] << " Dist from bear: " << vi[cur.ff][cur.ss]-wt+1 << ln;
				vi[cur.ff][cur.ss+1]=vi[cur.ff][cur.ss]+1;
				q.push({cur.ff, cur.ss+1});
			}
		}
		if (vi[hcor.ff][hcor.ss]<INF) return 1;
		else return 0;
	};
	for (auto hive:hvs){
		bfs1(hive);
	}
	ll l=0, r=n*n+1;
	while (l+1<r){
		ll mid = (l+r)/2;
		if (bfs2(mid)) {
			l=mid;
			// cout << mid << " with T" << ln;
		}
		else {
			r=mid;
			// cout << mid << " with F" << ln;
		}
	}
	if (bfs2(l))cout << l << ln;
	else cout << -1 << ln;
}

int main() {
	ll t=1; 
	// cin >> t;
	while (t--) solve();
}

• Subtask 1: 21 / 100