제출 #1103071

#제출 시각아이디문제언어결과실행 시간메모리
1103071ef10Mecho (IOI09_mecho)C++17
53 / 100
119 ms8440 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; int N,S; string M[1001]; struct node { int hd; int md; }; bool v[1001][1001]; node all[1001][1001]; pair<int,int> m; bool work(int e) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { all[i][j].md = -1; } } queue<pair<int,int> > q; q.push(m); all[m.first][m.second].md = 0; if (all[m.first][m.second].hd != -1 && all[m.first][m.second].hd <= e) return false; while (!q.empty()) { auto c = q.front(); //cout << "handling " << c.first << "/" << c.second << "/" << all[c.first][c.second].md << endl; int cost = all[c.first][c.second].md+1; q.pop(); for (auto i : {-1,1}) { for (int j = 0; j <= 1; j++) { int ti = j ? c.first : c.first+i; int tj = j ? c.second+i : c.second; if (ti < 0 || ti >= N || tj < 0 || tj >= N) continue; //cout << " " << ti << "/" << tj << " " << endl; if (M[ti][tj] == 'T') continue; if (all[ti][tj].md >= 0 && all[ti][tj].md <= cost) continue; if (all[ti][tj].hd >= 0 && all[ti][tj].hd <= cost/S+e) continue; if (M[ti][tj] == 'D') return true; //cout << " " << ti << "/" << tj << " passed" << endl; all[ti][tj].md = cost; q.push(make_pair(ti,tj)); //cout << " add q " << ti << "/" << tj << "/" << cost << endl; } } /*for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << all[i][j].md << " "; } cout << endl; }*/ } return false; } int solve() { int lo = 0, hi = 2*N; // if none of the values in the range work, return lo - 1 lo--; while (lo < hi) { // find the middle of the current range (rounding up) int mid = lo + (hi - lo + 1) / 2; //cout << "mid: " << mid << ", " << lo << "/" << hi << endl; if (work(mid)) { //cout << " worked" << endl; // if mid works, then all numbers smaller than mid also work lo = mid; } else { //cout << " not work" << endl; // if mid does not work, greater values would not work either hi = mid - 1; } } return lo; } int main() { cin >> N >> S; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { all[i][j].hd = -1; } } queue<pair<int,int> > q; for (int i = 0; i < N; i++) { cin >> M[i]; for (int j = 0; j < N; j++) { if (M[i][j] == 'H') { all[i][j].hd = 0; q.push(make_pair(i,j)); } else if (M[i][j] == 'M') { m = make_pair(i,j); } } } while (!q.empty()) { auto c = q.front(); int cost = all[c.first][c.second].hd+1; q.pop(); for (auto i : {-1,1}) { for (int j = 0; j <= 1; j++) { int ti = j ? c.first : c.first+i; int tj = j ? c.second+i : c.second; if (ti < 0 || ti >= N || tj < 0 || tj >= N) continue; if (M[ti][tj]=='T' || M[ti][tj]=='D' || (all[ti][tj].hd!=-1 && all[ti][tj].hd<=cost)) continue; all[ti][tj].hd = cost; q.push(make_pair(ti,tj)); //cout << "add " << ti << "/" << tj << endl; } } } /*for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << all[i][j].hd << " "; } cout << endl; }*/ int r = solve(); cout << r << endl; //cout << work(3) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...