Submission #1074369

#TimeUsernameProblemLanguageResultExecution timeMemory
1074369TheEpicCowOfLifeMecho (IOI09_mecho)C++14
100 / 100
219 ms3360 KiB
#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:10: 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:18: 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:9: warning: 'sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |         if (sz == 0) return false;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...