제출 #685122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685122		vjudge1	Mecho (IOI09_mecho)	C++11	58 / 100	373 ms	65536 KiB

mecho

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 805;
const int maxv = (int) 1e6+5;
int n,s,bval[maxn][maxn],mval[maxn][maxn];
char arr[maxn][maxn];
vector<pair<int,int> > bees,bconn[maxn][maxn],mconn[maxn][maxn];
pair<int,int> mecho,home;
bool isPoss(int time) {
    if(time*s >= bval[mecho.first][mecho.second]) return false;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            mval[i][j] = -1;
        }
    }
    mval[mecho.first][mecho.second] = time*s;
    queue<pair<int,int> > bfs;
    bfs.push(mecho);
    while(bfs.size() > 0) {
        pair<int,int> currP = bfs.front();
        bfs.pop();
        for(int i = 0; i < mconn[currP.first][currP.second].size(); i++) {
            pair<int,int> targP = mconn[currP.first][currP.second][i];
            if(targP == home) return true;
            if(mval[targP.first][targP.second] == -1 && bval[targP.first][targP.second] > mval[currP.first][currP.second]+1) {
                mval[targP.first][targP.second] = mval[currP.first][currP.second]+1;
                bfs.push(targP);
            }
        }
    }
    return false;
}
int main () {
    scanf("%d%d",&n,&s);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf(" %c",&arr[i][j]);
            if(arr[i][j] == 'H') bees.push_back(make_pair(i,j));
            if(arr[i][j] == 'M') mecho = make_pair(i,j);
            if(arr[i][j] == 'D') home = make_pair(i,j);
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(arr[i+1][j] == 'G' || arr[i+1][j] == 'M') bconn[i][j].push_back(make_pair(i+1,j));
            if(arr[i-1][j] == 'G' || arr[i-1][j] == 'M') bconn[i][j].push_back(make_pair(i-1,j));
            if(arr[i][j+1] == 'G' || arr[i][j+1] == 'M') bconn[i][j].push_back(make_pair(i,j+1));
            if(arr[i][j-1] == 'G' || arr[i][j-1] == 'M') bconn[i][j].push_back(make_pair(i,j-1));
            if(arr[i+1][j] == 'G' || arr[i+1][j] == 'M' || arr[i+1][j] == 'D') mconn[i][j].push_back(make_pair(i+1,j));
            if(arr[i-1][j] == 'G' || arr[i-1][j] == 'M' || arr[i-1][j] == 'D') mconn[i][j].push_back(make_pair(i-1,j));
            if(arr[i][j+1] == 'G' || arr[i][j+1] == 'M' || arr[i][j+1] == 'D') mconn[i][j].push_back(make_pair(i,j+1));
            if(arr[i][j-1] == 'G' || arr[i][j-1] == 'M' || arr[i][j-1] == 'D') mconn[i][j].push_back(make_pair(i,j-1));
            bval[i][j] = -1;
        }
    }
    queue<pair<int,int> > bfs;
    for(int i = 0; i < bees.size(); i++) {
        bfs.push(bees[i]);
        bval[bees[i].first][bees[i].second] = 0;
    }
    while(bfs.size() > 0) {
        pair<int,int> currP = bfs.front();
        bfs.pop();
        for(int i = 0; i < bconn[currP.first][currP.second].size(); i++) {
            pair<int,int> targP = bconn[currP.first][currP.second][i];
            if(bval[targP.first][targP.second] == -1) {
                bval[targP.first][targP.second] = bval[currP.first][currP.second]+s;
                bfs.push(targP);
            }
        }
    }
    int l = -5, r = maxv;
    while(l+1 < r) {
        int mid = (l+r)/2;
        if(isPoss(mid) == true) {
            l = mid;
        }
        else r = mid;
    }
    if(l >= 0) printf("%d\n",l);
    else printf("-1\n");
    return 0;
}

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

mecho.cpp: In function 'bool isPoss(int)':
mecho.cpp:24:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 0; i < mconn[currP.first][currP.second].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < bees.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
mecho.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(int i = 0; i < bconn[currP.first][currP.second].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d%d",&n,&s);
      |     ~~~~~^~~~~~~~~~~~~~
mecho.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |             scanf(" %c",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 58 / 100