Submission #1275206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275206		sonarcht	Mecho (IOI09_mecho)	C++20	100 / 100	208 ms	21304 KiB

mecho

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef map<ll,ll> mll;
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll maxn = 8e2 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, k, ans = -1, a[maxn][maxn], b[maxn][maxn], dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
map<char,ll> m = {{'G', 0}, {'T', 1}, {'M', 2}, {'D', 3}, {'H', 4}};
pll posm, posd;

bool check(ll x, ll y, ll a[maxn][maxn]) {
	if (x < 1 || x > n || y < 1 || y > n) return 0;
	if (a[x][y] == 1 || a[x][y] == 4) return 0;
	return 1;
}

queue<pll> q;
ll dist[maxn][maxn];
void multisource_bfs() {
	fill(&dist[0][0], &dist[maxn][0], inf);
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) {
		if (a[i][j] == 4) q.push({i,j}), dist[i][j] = 0;
	}
	while (!q.empty()) {
		auto [x,y] = q.front();
		q.pop();
		for (int d = 0; d < 4; ++d) {
			ll nx = x + dir[d][0], ny = y + dir[d][1];
			if (!check(nx,ny,a) || a[nx][ny] == 3) continue;
			if (dist[nx][ny] == inf) {
				dist[nx][ny] = dist[x][y] + k;
				q.push({nx,ny});
			}
		}
		
	}
}

void build(ll mid) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (check(i,j,a) && dist[i][j] <= mid) b[i][j] = 4;
			else b[i][j] = a[i][j];
		}
	}
}

ll distm[maxn][maxn];
bool can_reach(ll x, ll y, ll mid) {
	if (distm[x][y] + mid*k < dist[x][y]) return 1;
	return 0;
}

void bfs(ll mid) {
	while (!q.empty()) q.pop();
	fill(&distm[0][0], &distm[maxn][0], inf);
	auto [mx,my] = posm;
	distm[mx][my] = 0;
	if (can_reach(mx,my,mid)) q.push(posm);
	while (!q.empty()) {
		auto [x,y] = q.front();
		q.pop();
		for (int d = 0; d < 4; ++d) {
			ll nx = x + dir[d][0], ny = y + dir[d][1];
			if (!check(nx,ny,b)) continue;
			if (distm[nx][ny] == inf) {
				distm[nx][ny] = distm[x][y] + 1;
				if (can_reach(nx,ny,mid)) q.push({nx,ny});
			}
		}
	}
}

bool checkbs(ll mid) {
	auto [dx,dy] = posd;
	auto [mx,my] = posm;
	if (b[mx][my] == 4) return 0;
	for (int d = 0; d < 4; ++d) {
		ll x = dx + dir[d][0], y = dy + dir[d][1];
		if (!check(x,y,a) || distm[x][y] == inf) continue;
		if (can_reach(x,y,mid)) return 1;
		if ((distm[x][y]+k-1) / k == dist[x][y] - mid && distm[x][y] % k != 0) return 1;
	}
	return 0;
}

void out(ll a[maxn][maxn]) {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			cout << (a[i][j] == inf ? -1 : a[i][j]) << " ";
			//cout << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		string s;
		cin >> s;
		s = " " + s;
		for (int j = 1; j <= n; ++j) {
			a[i][j] = m[s[j]];
			if (a[i][j] == 2) posm = {i,j};
			if (a[i][j] == 3) posd = {i,j};
		}
	}
	multisource_bfs();
	//out(dist);
	ll l = 0, r = n*n;
	while (l <= r) {
		ll mid = (l+r) / 2;
		build(mid);
		bfs(mid);
		//out(b);
		//out(distm);
		if (checkbs(mid)) {
			ans = mid;
			l = mid+1;
		} else r = mid-1;
	}
	cout << ans;
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (fopen(".INP", "r")) {
		freopen(".INP", "r", stdin);
		freopen(".OUT", "w", stdout);
	}
	ll testCase = 1;
//	cin >> testCase;
	while (testCase--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:132:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:133:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100