Submission #541302

#TimeUsernameProblemLanguageResultExecution timeMemory
541302SquareSpoonMecho (IOI09_mecho)C++14
20 / 100
137 ms5936 KiB
#include <iostream> #include <queue> #include <utility> #include <vector> #include <algorithm> #define MAX 801 using namespace std; typedef pair<int, int> pii; int n, m, d[MAX][MAX]; char map[MAX][MAX]; bool v[MAX][MAX]; int x[5] = {1, 0, -1, 0}; int y[5] = {0, 1, 0, -1}; //calcular o tempo em passos void bees(vector<pii> c){ queue<pii> q; for(int i = 0; i < c.size(); i++){ q.push(c[i]); d[c[i].first][c[i].second] = m; } while(!q.empty()){ pii node = q.front(); q.pop(); if(v[node.first][node.second]) continue; v[node.first][node.second] = true; for(int i = 0; i < 4; i++){ int x1 = x[i] + node.first; int y1 = y[i] + node.second; if(x1 > n || x1 < 1 || y1 > n || y1 < 1) continue; if(v[x1][y1]) continue; if(d[x1][y1] > d[node.first][node.second] + 1 || d[x1][y1] == 0) d[x1][y1] = d[node.first][node.second] + m; q.push(make_pair(x1, y1)); } } } int bfs(int c1, int c2, int steps, int time){ queue<pair<int, pii > > q; bool v2[MAX][MAX]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) v2[i][j] = false; q.push(make_pair(time, make_pair(c1, c2))); while(!q.empty()){ pii node = q.front().second; int stps = q.front().first; q.pop(); if(v2[node.first][node.second]) continue; v2[node.first][node.second] = true; for(int i = 0; i < 4; i++){ int x1 = x[i] + node.first; int y1 = y[i] + node.second; if(x1 < 1 || x1 > n || y1 < 1 || y1 > n) continue; //cout << x1 << " " << y1 << " " << d[x1][y1] << " " << map[x1][y1] << " " << v2[x1][y1] << '\n'; if(v2[x1][y1] || map[x1][y1] == 'T' || d[x1][y1] <= stps || map[x1][y1] == 'H' || map[x1][y1] == 'M') continue; //cout << stps << '\n'; //cout << x1 << " " << y1 << " " << d[x1][y1] << '\n'; if(map[x1][y1] == 'D'){ //cout << "found" << '\n'; int res = stps/m; return res; } q.push(make_pair(stps+1, make_pair(x1, y1))); } } return -1; } int main(){ cin >> n >> m; vector<pii> cords; int xs, ys, xs1, ys1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cin >> map[i][j]; if(map[i][j] == 'H'){ cords.push_back(make_pair(i, j)); } else if(map[i][j] == 'D'){ xs = i, ys = j; } else if(map[i][j] == 'M'){ xs1 = i, ys1 = j; } } } bees(cords); int limit = 0; for(int i = 0; i < 4; i++){ int x1 = xs + x[i]; int y1 = ys + y[i]; if(x1 > n || x1 < 1 || y1 < 1 || y1 > n) continue; limit = max(limit, d[x1][y1]); } int l = 1, r = (limit - m)/m; int mid = (l+r)/2; int res = -1; int path; d[xs][ys] = MAX*m; while(l <= r){ path = bfs(xs1, ys1, m, mid*m); //cout << path << '\n'; if(path == -1){ r = mid - 1; } else{ l = mid + 1; res = max(res, mid); } //cout << mid << " "; mid = (l+r)/2; path = 0; } cout << res-1 << '\n'; //cout << path << " " << time << '\n'; /*for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout << d[i][j] << " "; } cout << '\n'; }*/ }

Compilation message (stderr)

mecho.cpp: In function 'void bees(std::vector<std::pair<int, int> >)':
mecho.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int i = 0; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
mecho.cpp: In function 'int main()':
mecho.cpp:98:17: warning: 'ys1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |       path = bfs(xs1, ys1, m, mid*m);
      |              ~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:88:11: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
   88 |       int y1 = ys + y[i];
      |           ^~
mecho.cpp:98:17: warning: 'xs1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |       path = bfs(xs1, ys1, m, mid*m);
      |              ~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:87:11: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |       int x1 = xs + x[i];
      |           ^~
#Verdict Execution timeMemoryGrader output
Fetching results...