Submission #1074478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074478		TheEpicCowOfLife	Mecho (IOI09_mecho)	C++14	100 / 100	239 ms	3404 KiB

mecho

    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <algorithm>
    #include <utility>
    #include <cstring>
     
    using namespace std;
     
    typedef pair<int,int> pii;
     
    bool is_g[805][805];
    bool pushed[805][805];
     
    bool bocc[805][805];
     
    int sx, sy;
    int fx, fy;
     
    int n,s;
     
    vector<pii> hv;
     
    queue<pii> mq;
    queue<pii> bq;
     
    int ax[4] = {0,1,0,-1};
    int ay[4] = {1,0,-1,0};
    // can mecho make it back to the hive waiting k minutes?
    bool decision(int k){
        queue<pii> mq;
        queue<pii> bq;
        memset(pushed, 0, sizeof(pushed));
        memset(bocc, 0, sizeof(bocc));
        mq.push({sx,sy});
        pushed[sx][sy] = true;
        for (pii cur : hv){
            bq.push(cur);
            bocc[cur.first][cur.second] = true;
        }
     
        for (int vi = 0; vi < k; vi++){
            int sz = bq.size();
            for (int i = 0 ; i < sz; i++){
                pii cur = bq.front();
                bq.pop();
                for (int j = 0; j < 4; j++){
                    int cx = cur.first + ax[j];
                    int cy = cur.second + ay[j];
                    if (!bocc[cx][cy] && is_g[cx][cy]){
                        bocc[cx][cy] = true;
                        bq.push({cx,cy});
                    }
                }
            }
        }
     
        while(true){
            int sz;
            for (int vi = 0; vi < s; vi++){
                sz = mq.size();
                for (int i = 0 ; i < sz; i++){
                    pii cur = mq.front();
                    mq.pop();
                    if (bocc[cur.first][cur.second]) continue;
                    for (int j = 0; j < 4; j++){
                        int cx = cur.first + ax[j];
                        int cy = cur.second + ay[j];
                        if (cx == fx && cy == fy) return true;
                        if (!bocc[cx][cy] && is_g[cx][cy] && !pushed[cx][cy]){
                            pushed[cx][cy] = true;
                            mq.push({cx,cy});
                        }
                    }
                }
            }
            if (sz == 0) return false;
            sz = bq.size();
            for (int i = 0 ; i < sz; i++){
                pii cur = bq.front();
                bq.pop();
                for (int j = 0; j < 4; j++){
                    int cx = cur.first + ax[j];
                    int cy = cur.second + ay[j];
                    if (!bocc[cx][cy] && is_g[cx][cy]){
                        bocc[cx][cy] = true;
                        bq.push({cx,cy});
                    }
                }
            }
        }
     
    }
     
    int main(){
        scanf("%d %d", &n, &s);
        for (int y = 1; y <= n; y++){
            for (int x = 1; x <= n; x++){
                char inst;
                scanf(" %c", &inst);
                if (inst == 'G'){
                    is_g[x][y] = true;
                }
                else if (inst == 'H'){
                    hv.push_back({x,y});
                }
                else if (inst == 'M'){
                    sx = x;
                    sy = y;
                    is_g[x][y] = true;
                }
                else if (inst == 'D'){
                    fx = x;
                    fy = y;
                }
            }
        }
     
        int best = -1;
        int lo = 0;
        int hi = n * n/2 + 1;
        while (lo <= hi){
            int mid = (lo + hi)/2;
            if (decision(mid)){
                lo = mid + 1;
                best = mid;
            }
            else{
                hi = mid - 1;
            }
        }
     
        printf("%d\n", best);
     
    }

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         scanf("%d %d", &n, &s);
      |         ~~~~~^~~~~~~~~~~~~~~~~
mecho.cpp:100:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |                 scanf(" %c", &inst);
      |                 ~~~~~^~~~~~~~~~~~~~
mecho.cpp: In function 'bool decision(int)':
mecho.cpp:77:13: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             if (sz == 0) return false;
      |             ^~

• Subtask 1: 100 / 100