# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
957744 | hirayuu_oj | Mecho (IOI09_mecho) | C++17 | 182 ms | 11860 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,a,b) for(int i=a; i<(b); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;
const int four[5]={0,1,0,-1,0};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll s;
cin>>n>>s;
vector<string> forest(n);
rep(i,n){
cin>>forest[i];
}
vector<vector<ll>> bee(n,vector<ll>(n,INF));
queue<pair<int,int>> vert;
rep(i,n){
rep(j,n){
if(forest[i][j]=='H'){
bee[i][j]=0;
vert.push({i,j});
}
}
}
while(!vert.empty()){
int x,y;
tie(x,y)=vert.front();
vert.pop();
rep(i,4){
int nx=x+four[i],ny=y+four[i+1];
if(nx<0 or n<=nx or ny<0 or n<=ny){
continue;
}
if(forest[nx][ny]!='G'){
continue;
}
if(bee[nx][ny]>bee[x][y]+1){
bee[nx][ny]=bee[x][y]+1;
vert.push({nx,ny});
}
}
}
int hx,hy;
rep(i,n){
rep(j,n){
if(forest[i][j]=='D'){
hx=i;
hy=j;
}
}
}
ll ok=-1,ng=n*n+1000;
vector<vector<ll>> dist(n,vector<ll>(n));
while(ng-ok>1){
ll mid=(ok+ng)>>1;
rep(i,n){
rep(j,n){
if(forest[i][j]=='M'){
dist[i][j]=mid*s;
vert.push({i,j});
}
else{
dist[i][j]=INF;
}
}
}
bool can=false;
while(!vert.empty()){
int x,y;
tie(x,y)=vert.front();
vert.pop();
rep(i,4){
int nx=x+four[i],ny=y+four[i+1];
if(nx<0 or n<=nx or ny<0 or n<=ny){
continue;
}
if(forest[nx][ny]=='D'){
can=true;
}
if(forest[nx][ny]!='G'){
continue;
}
if((dist[x][y]+1)/s>=bee[nx][ny]){
continue;
}
if(dist[nx][ny]>dist[x][y]+1){
dist[nx][ny]=dist[x][y]+1;
vert.push({nx,ny});
}
}
}
if(can){
ok=mid;
}
else{
ng=mid;
}
}
cout<<ok<<"\n";
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |