제출 #1013345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013345		ducksaysquack	Mecho (IOI09_mecho)	C++98	100 / 100	167 ms	12236 KiB

mecho

#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
int n, m;
int C[]{0,1,0,-1}, R[]{1,0,-1,0};
pair<int,int> a, b; queue<pair<int,int>> q;
vector<vector<int>> g(805, vector<int>(805, 1e9));
vector<string> v(805);
bool bfs(int k) {
	vector<vector<int>> dis(n, vector<int>(n, 1e9));
	q.push(a); dis[a.f][a.s] = 0;
    while(!q.empty()) {
    	pair<int,int> r = q.front(); q.pop();
    	for(int i=0;i<4;i++) {
    		int x = r.f+R[i], y = r.s+C[i];
    		if(0 <= x && x < n && 0 <= y && y < n && ((dis[r.f][r.s]+1)/m < g[x][y]-k && v[x][y] != 'D' || (dis[r.f][r.s]+1)/m <= g[r.f][r.s]-k && v[x][y] == 'D'))
    			if(dis[r.f][r.s]+1 < dis[x][y] && (v[x][y] == 'G' || v[x][y] == 'D')) {
    				dis[x][y] = dis[r.f][r.s]+1;
    				q.push({x,y});
    			}
    	}
    }
    if(dis[b.f][b.s] == 1e9) return false;
    return true;
}
signed main() {
    //ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m; for(int i=0;i<n;i++) cin >> v[i];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) {
    	if(v[i][j] == 'M') a.f = i, a.s = j;
    	if(v[i][j] == 'D') b.f = i, b.s = j;
    	if(v[i][j] == 'H') {q.push({i,j}); g[i][j] = 0;}
    }
    while(!q.empty()) {
    	pair<int,int> r = q.front(); q.pop();
    	for(int i=0;i<4;i++) {
    		int x = r.f+R[i], y = r.s+C[i];
    		if(0 <= x && x < n && 0 <= y && y < n) if(g[r.f][r.s]+1 < g[x][y] && (v[x][y] == 'G' || v[x][y] == 'M')) {
    			g[x][y] = g[r.f][r.s]+1;
    			q.push({x,y});
    		}
    	}
    }
    int l = -1, r = g[a.f][a.s]-1;
    while(l<r) {
    	int d = (l+r+1)/2;
    	if(bfs(d)) l = d;
    	else r = d-1;
    }
    cout << l;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'bool bfs(long long int)':
mecho.cpp:18:81: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |       if(0 <= x && x < n && 0 <= y && y < n && ((dis[r.f][r.s]+1)/m < g[x][y]-k && v[x][y] != 'D' || (dis[r.f][r.s]+1)/m <= g[r.f][r.s]-k && v[x][y] == 'D'))
      |                                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100