Submission #685124

#	Time	Username	Problem	Language	Result	Execution time	Memory
685124		vjudge1	Mecho (IOI09_mecho)	C++11	100 / 100	436 ms	52232 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];
bool isH[maxn][maxn];
vector<pair<int,int> > bees,conn[maxn][maxn];
pair<int,int> mecho;
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();
        if(isH[currP.first][currP.second] == true) return true;
        bfs.pop();
        for(int i = 0; i < conn[currP.first][currP.second].size(); i++) {
            pair<int,int> targP = conn[currP.first][currP.second][i];
            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') {
                isH[i+1][j] = true;
                isH[i-1][j] = true;
                isH[i][j+1] = true;
                isH[i][j-1] = true;
            }
        }
    }
    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') conn[i][j].push_back(make_pair(i+1,j));
            if(arr[i-1][j] == 'G' || arr[i-1][j] == 'M') conn[i][j].push_back(make_pair(i-1,j));
            if(arr[i][j+1] == 'G' || arr[i][j+1] == 'M') conn[i][j].push_back(make_pair(i,j+1));
            if(arr[i][j-1] == 'G' || arr[i][j-1] == 'M') conn[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 < conn[currP.first][currP.second].size(); i++) {
            pair<int,int> targP = conn[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;
}

Compilation message (stderr)

mecho.cpp: In function 'bool isPoss(int)':
mecho.cpp:26: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]
   26 |         for(int i = 0; i < conn[currP.first][currP.second].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:61: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]
   61 |     for(int i = 0; i < bees.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
mecho.cpp:68: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]
   68 |         for(int i = 0; i < conn[currP.first][currP.second].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d%d",&n,&s);
      |     ~~~~~^~~~~~~~~~~~~~
mecho.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |             scanf(" %c",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100