제출 #482570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482570		BackNoob	Mecho (IOI09_mecho)	C++14	14 / 100	337 ms	9184 KiB

mecho

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
using namespace std;
const int mxN = 1007;
const ll inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int n , limit;
char a[mxN][mxN];
int bee[mxN][mxN];
int dist[mxN][mxN];
pair<int , int> mecho , home;
int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};

bool ok(int x)
{
	for(int i = 0 ; i <= n ; i++)
	for(int j = 0 ; j <= n ; j++) dist[i][j] = inf;
	queue<pair<int , int>> q;
	q.push(mecho);
	dist[mecho.fi][mecho.se] = limit * x;

	while(!q.empty()) {
		int x = q.front().fi;
		int y = q.front().se;
		q.pop();

		for(int d = 0 ; d < 4 ; d++) {
			int newx = x + dx[d];
			int newy = y + dy[d];
			if(1 <= newx && newx <= n && 1 <= newy && newy <= n && a[newx][newy] == 'G') {
				if(dist[newx][newy] > dist[x][y] + 1 && bee[newx][newy] > (dist[x][y] + 1) / limit) {
					dist[newx][newy] = dist[x][y] + 1;
					q.push({newx , newy});
				}
			}
		}
	}

	if(dist[home.fi][home.se] != dist[0][0]) return true;
	return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);
    
    cin >> n >> limit;
    for(int i = 1 ; i <= n ; i++)
    for(int j = 1 ; j <= n ; j++) cin >> a[i][j];

    memset(bee, 0x3f, sizeof bee);
    queue<pair<int , int>> q;
    for(int i = 1 ; i <= n ; i++)
    for(int j = 1 ; j <= n ; j++) {
    	if(a[i][j] == 'H') {
    		bee[i][j] = 0;
    		q.push({i , j});
    	}
    	if(a[i][j] == 'M') mecho = {i , j};
    	if(a[i][j] == 'D') home = {i , j};
    }

    a[home.fi][home.se] = 'G';

    while(!q.empty()) {
    	int x = q.front().fi;
    	int y = q.front().se;
    	q.pop();

    	for(int d = 0 ; d < 4 ; d++) {
    		int newx = x + dx[d];
    		int newy = y + dy[d];
    		if(1 <= newx && newx <= n && 1 <= newy && newy <= n && a[newx][newy] == 'G') {
    			if(bee[newx][newy] > bee[x][y] + 1) {
    				bee[newx][newy] = bee[x][y] + 1;
    				q.push({newx , newy});
    			}
    		}
    	}
    }

    int lo = 0 , hi = inf;
    while(lo + 1 < hi) {
    	int mid = (lo + hi) / 2;
    	if(ok(mid)) lo = mid;
    	else hi = mid;
    }

    if(ok(lo) == false) cout << -1;
    else cout << lo;

    return 0;
}

• Subtask 1: 14 / 100