제출 #1020095

#제출 시각아이디문제언어결과실행 시간메모리
1020095parentoniMecho (IOI09_mecho)C++17
84 / 100
211 ms11084 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define print(x) for (auto el: x) cout << el << " "; cout << '\n' #define f first #define s second using ll = long long; using llb = long double; using vl = vector<ll>; using pll = pair<ll,ll>; // functions void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);} void yes() { cout<<"YES\n"; } void no() { cout<<"NO\n"; } // geometry const double PI = 3.14159265358979323846; double DEG_to_RAD (double d) {return d*PI/180.0;} double RAD_to_DEG (double r) {return r*180.0/ PI;} // values const ll INF = 1e18; const ll MOD = 1000000007; const ll MAX_N = 800; ll dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1}; pll m, house; ll n, s, db[MAX_N][MAX_N]; queue<pll> qb; bitset<MAX_N> b[MAX_N]; // board; bool possible(ll min) { vector<vl> d(n, vl(n, -1)); queue<pll> q; q.push(m); d[m.f][m.s] = 0; while(q.size()) { pll a = q.front(); q.pop(); for (int i=0;i<4;i++) { ll x = a.f + dx[i], y = a.s + dy[i], c = d[a.f][a.s] + 1; if (x == house.f && y == house.s) return true; if (x < 0 || x >= n || y < 0 || y >= n) continue; if (!b[x][y] || d[x][y] != -1) continue; if (c/s + min >= db[x][y]) continue; d[x][y] = c; q.push({x,y}); } } return false; } ll last_true(ll lo, ll hi, function<bool(ll)> f) { ll ans = -1; while(lo <= hi) { ll med = (hi-lo)/2 + lo; if (f(med)) { lo = med + 1; ans = med; } else { hi = med - 1; } } return ans; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> s; for (auto &row: db) for (auto &el: row) el = -1; for (int i=0;i<n;i++) { string t; cin >> t; for (int j=0;j<n;j++) { b[i][j] = t[j] == 'G'; if (t[j] == 'H') { db[i][j] = 0; qb.push({i,j}); } if (t[j] == 'M') { m = {i,j}; } if (t[j] == 'D') { house = {i,j}; } } } while(qb.size()) { pll a = qb.front(); qb.pop(); for (int i=0;i<4;i++) { ll x = a.f + dx[i], y = a.s + dy[i]; if (x < 0 || x >= n || y < 0 || y >= n) continue; if (!b[x][y] || db[x][y] != -1) continue; db[x][y] = db[a.f][a.s]+1; qb.push({x,y}); } } cout << last_true(0, 1e17, possible) << endl; }

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'void setIO(std::string)':
mecho.cpp:15:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mecho.cpp:15:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 | void setIO(string s) {freopen((s + ".in").c_str(), "r", stdin);freopen((s + ".out").c_str(), "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...