# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
683266 | ajstillpracticin | Mecho (IOI09_mecho) | C++17 | 534 ms | 7692 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int dx[4]{1,0,-1,0};
int dy[4]{0,1,0,-1};
char direc[4]{'R','U','L','D'};
void setIO(string filename=""){
ios_base::sync_with_stdio(0); cin.tie(0);
if(filename.size()){
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
}
const int INF=(int) 1e9;
const int M= 1e9+7;
const ll MAXD = 1e18;
//
const int MAXN = 1e4;
int main() {
setIO();
int n,s;
cin >> n >> s;
string grid[n];
for(int i=0;i<n;++i)
cin >> grid[i];
vector<pair<int,int>> hive;
int mechox,mechoy,homex,homey;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
if(grid[i][j]=='M'){
mechox=i;
mechoy=j;
} else if(grid[i][j]=='H'){
hive.push_back({i,j});
} else if(grid[i][j]=='D'){
homex=i;
homey=j;
}
}
int l=0;
int r=n*n;
while(l<=r){
bool bee_vis[n][n]{};
bool me_vis[n][n]{};
int bee_time[n][n];
int me_time[n][n];
memset(bee_time, 0 , sizeof(bee_time));
memset(me_time, 0 , sizeof(me_time));
int time=(l+r)/2;
queue<pair<int,int>> q;
for(auto i : hive){
q.push({i.fi,i.se});
bee_vis[i.fi][i.se]=1;
}
while(!q.empty()){
int x=q.front().fi;
int y=q.front().se;
q.pop();
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n)
continue;
if(!(grid[nx][ny]=='G' || grid[nx][ny]=='M') || bee_vis[nx][ny])
continue;
bee_time[nx][ny]=bee_time[x][y]+1;
q.push({nx,ny});
bee_vis[nx][ny]=1;
}
}
q.push({mechox,mechoy});
me_vis[mechox][mechoy]=1;
if(bee_time[mechox][mechoy]<=time)
q.pop();
while(!q.empty()){
int x=q.front().fi;
int y=q.front().se;
q.pop();
for(int i=0;i<4;++i){
int nx=x+dx[i],ny=y+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n)
continue;
if(!(grid[nx][ny]=='G' || grid[nx][ny]=='M') || me_vis[nx][ny])
continue;
if((me_time[x][y]+1)/s < bee_time[nx][ny]-time){
me_vis[nx][ny]=1;
q.push({nx,ny});
me_time[nx][ny]=me_time[x][y]+1;
}
}
}
bool ans=0;
for(int i=0;i<4;++i){
int nx=homex+dx[i],ny=homey+dy[i];
if(nx<0 || nx>=n || ny<0 || ny>=n)
continue;
if((me_time[nx][ny]/s)<bee_time[nx][ny]-time && me_vis[nx][ny]){
ans=1;
break;
}
}
if(ans)
l=time+1;
else
r=time-1;
}
cout << l-1 << "\n";
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |