Submission #531012

#	Time	Username	Problem	Language	Result	Execution time	Memory
531012		Alan	Mecho (IOI09_mecho)	C++17	100 / 100	146 ms	4444 KiB

mecho

#include <bits/stdc++.h>
#define I using
#define WA using namespace std;
#define on using ll = long long;
#define Test(x) int AlanIQ = -(x);
#define should ld =
#define quit long double;
#define OI int
#define forever main
#define Alan cin.tie(0);
#define fai(x) ios::ios_base::sync_with_stdio(!x);
#define Sharky return
#define orz 0;

WA on Test (109)

struct bee {
	int r, c, t;
};

int grid[801][801], startr, startc, endr, endc;
bool vi[801][801];

bool ok (int n, int s, int diff) {
	if (grid[startr][startc] - diff <= 0) return false;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) vi[i][j] = false;
	queue<bee> q;
	q.push({startr, startc, 0});
	vi[startr][startc] = true;
	while (!q.empty()) {
		int r = q.front().r;
		int c = q.front().c;
		int t = q.front().t;
		int tt = (t+2) / s + !!((t+2) % s);
		q.pop();
		if (c < n-1 && tt < grid[r][c+1] - diff + 1 && grid[r][c+1] != 1e9 && !vi[r][c+1]) {q.push({r, c+1, t+1}); vi[r][c+1] = true;}
		if (c > 0 && tt < grid[r][c-1] - diff + 1&& grid[r][c-1] != 1e9 && !vi[r][c-1]) {q.push({r, c-1, t+1}); vi[r][c-1] = true;}
		if (r < n-1 && tt < grid[r+1][c] - diff + 1 && grid[r+1][c] != 1e9 && !vi[r+1][c]) {q.push({r+1, c, t+1}); vi[r+1][c] = true;}
		if (r > 0 && tt < grid[r-1][c] - diff + 1 && grid[r-1][c] != 1e9 && !vi[r-1][c]) {q.push({r-1, c, t+1}); vi[r-1][c] = true;}
	}
	return vi[endr][endc];
}

I should quit OI forever () {
	Alan fai (true)
	int n, s;
	char ch;
	cin >> n >> s;
	queue<bee> q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> ch;
			if (ch == 'T') grid[i][j] = 1e9;
			else if (ch == 'G') grid[i][j] = 0;
			else if (ch == 'M') {
				startr = i;
				startc = j;
				grid[i][j] = 0;
			} else if (ch == 'D') {
				endr = i;
				endc = j;
				grid[i][j] = 1e8;
			} else if (ch == 'H') {
				q.push({i, j, 0});
				grid[i][j] = 1e9;
			}
		}
	}
	while (!q.empty()) {
		int r = q.front().r;
		int c = q.front().c;
		int t = q.front().t;
		q.pop();
		if (c < n-1 && !grid[r][c+1]) {q.push({r, c+1, t+1}); grid[r][c+1] = t+1;}
		if (c > 0 && !grid[r][c-1]) {q.push({r, c-1, t+1}); grid[r][c-1] = t+1;}
		if (r < n-1 && !grid[r+1][c]) {q.push({r+1, c, t+1}); grid[r+1][c] = t+1;}
		if (r > 0 && !grid[r-1][c]) {q.push({r-1, c, t+1}); grid[r-1][c] = t+1;}
	}
	
	int l = -1, r = n*n/2;
	while (l < r) {
		int mid = l + (r - l + 1) / 2;
		if (ok(n, s, mid)) l = mid;
		else r = mid-1;
	}

	cout << l << "\n";

	Sharky orz
}

• Subtask 1: 100 / 100