Submission #953300

#TimeUsernameProblemLanguageResultExecution timeMemory
953300snowmanMecho (IOI09_mecho)C++17
0 / 100
281 ms6500 KiB
#include <bits/stdc++.h> using namespace std; //Soltan Cristian #define ll long long #define all(x) x.begin(), x.end() #define mod 1000000007 #define pb push_back #define st first #define nd second #define sz(x) (ll)x.size() #define rall(x) x.rbegin(), x.rend() const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; const int mxa = 2 * 1e5 + 2; // string __fname = "maxflow"; // ifstream in(__fname + ".in"); // ofstream out (__fname + ".out"); // #define cin in // #define cout out int n, s; vector<vector<char>> mapa; bool validB(int x, int y){ if(x >= 0 && x < n && y >= 0 && y < n && mapa[x][y] != 'T' && mapa[x][y] != 'D'){ return true; } return false; } bool valid(int x, int y){ if(x >= 0 && x < n && y >= 0 && y < n && mapa[x][y] != 'T'){ return true; } return false; } void solve(){ cin >> n >> s; mapa = vector<vector<char>>(n, vector<char>(n)); vector<pair<int,int>> stup; pair<int, int> start, finish; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ char x; cin >> x; if(x == 'H') stup.pb({i, j}); if(x == 'M') start = {i, j}; if(x == 'D') finish = {i, j}; mapa[i][j] = x; } } vector<vector<int>> bees(n, vector<int>(n, INT_MAX)); queue<pair<int, int>> qB; for(int i = 0; i < sz(stup); i++){ bees[stup[i].st][stup[i].nd] = 0; qB.push({stup[i].st, stup[i].nd}); } // cout << "a\n"; while(!qB.empty()){ pair<int, int> u = qB.front(); qB.pop(); for(int i = 0; i < 4; i++){ if(!validB(u.st + dx[i], u.nd + dy[i])) continue; if(bees[u.st][u.nd] + s < bees[u.st + dx[i]][u.nd + dy[i]]){ qB.push({u.st + dx[i], u.nd + dy[i]}); bees[u.st + dx[i]][u.nd + dy[i]] = bees[u.st][u.nd] + s; } } } if(bees[start.st][start.nd] == INT_MAX){ cout << -1 << '\n'; return; } int l = 0, r = 2 * n * n; int ans = -1; while(l <= r){ int mid = (l + r) / 2; vector<vector<int>> h(n, vector<int>(n, INT_MAX)); h[start.st][start.nd] = mid; queue<pair<int,int>> q; q.push({start.st, start.nd}); while(!q.empty()){ pair<int, int> u = q.front(); q.pop(); for(int i = 0; i < 4; i++){ if(!valid(u.st + dx[i], u.nd + dy[i])) continue; if(h[u.st][u.nd] + 1 < bees[u.st + dx[i]][u.nd + dy[i]] && h[u.st][u.nd] + 1 < h[u.st + dx[i]][u.nd + dy[i]]){ q.push({u.st + dx[i], u.nd + dy[i]}); h[u.st + dx[i]][u.nd + dy[i]] = h[u.st][u.nd] + 1; } } } if(h[finish.st][finish.nd] < INT_MAX){ cout << mid << ' ' << ans << '\n'; ans = max(ans, mid); l = mid + 1; } else r = mid - 1; } // cout << ans << '\n'; // if(ans == -1){ // cout << -1<< '\n'; // } // else cout << ans / s << '\n'; } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << (setprecision(10)); // int t; // cin >> t; // while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...