제출 #661184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
661184		kirakaminski968	Mecho (IOI09_mecho)	C++11	100 / 100	251 ms	7252 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
int n,s;
string matrix[805];
int mechox, mechoy,homex,homey;
vector<pair<int,int>> hives;
bool validsquare(int x, int y){
    return x>=0 && x<n && y>=0 && y<n && (matrix[x][y] == 'G' || matrix[x][y] == 'M');
}
bool mecho_reached(int mecho_dis, int bees_dis){
	return mecho_dis / s < bees_dis;
}
int main()
{
    cin >> n >> s;
    for(int i = 0;i<n;i++){
        cin >> matrix[i];
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(matrix[i][j] == 'M'){
                mechox = i;
                mechoy = j;
            }
            if(matrix[i][j] == 'D'){
                homex = i;
                homey = j;
            }
            if(matrix[i][j] == 'H'){
                hives.push_back(make_pair(i,j));
            }
        }
    }
    queue<pair<int,int>> q;
    vector<vector<bool>> beesvis(n,vector<bool>(n));
    vector<vector<int>> beestime(n,vector<int>(n));
    for(auto hive: hives){
        q.push({hive.first,hive.second});
        beesvis[hive.first][hive.second] = true;
    }
    int dx[] = {0,-1,0,1};
    int dy[] = {-1,0,1,0};
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0;i<4;i++){
            int newx = x+dx[i],newy=y+dy[i];
            if(validsquare(newx,newy) && !beesvis[newx][newy]){
                beestime[newx][newy] = beestime[x][y]+1;
                q.push({newx,newy});
                beesvis[newx][newy] = true;
            }
        }
    }
    int l = 0, r = n*n;
    while(l<=r){
        vector<vector<bool>> mechovis(n,vector<bool>(n));
        vector<vector<int>> mechotime(n,vector<int>(n));
        queue<pair<int,int>> q2;
        int mid = (l+r)/2;
        q2.push({mechox,mechoy});
        mechovis[mechox][mechoy] = true;
        if(beestime[mechox][mechoy] <= mid){
            q2.pop();
        }
        while(!q2.empty()){
            int x = q2.front().first;
            int y = q2.front().second;
            q2.pop();
            for(int i = 0;i<4;i++){
                int newx = x+dx[i],newy=y+dy[i];
                if(validsquare(newx,newy) && !mechovis[newx][newy] && mecho_reached(mechotime[x][y] + 1, beestime[newx][newy] - mid)){
                    mechotime[newx][newy] = mechotime[x][y]+1;
                    q2.push({newx,newy});
                    mechovis[newx][newy] = true;
                }
            }
        }
        bool good = false;
        for(int i = 0;i<4;i++){
            int nx = homex+dx[i],ny = homey+dy[i];
            if(validsquare(nx,ny) && mechovis[nx][ny] && mecho_reached(mechotime[nx][ny],beestime[nx][ny]-mid)){
                good = true;
                break;
            }
        }
        if(good){
            l = mid+1;
        }
        else{
            r = mid-1;
        }
    }
    cout << l-1 << endl;
    return 0;
}

• Subtask 1: 100 / 100