Submission #1078903

#TimeUsernameProblemLanguageResultExecution timeMemory
1078903Yang8onMecho (IOI09_mecho)C++17
5 / 100
213 ms65536 KiB
#include <bits/stdc++.h> #define Y8o "main" #define maxn (int) 805 #define ll long long #define pii pair<int, int> #define gb(i, j) ((i >> j) & 1) #define all(x) x.begin(), x.end() #define _left id * 2, l, mid #define _right id * 2 + 1, mid + 1, r #define f first #define s second using namespace std; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll GetRandom(ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rng); } void iof() { if(fopen(Y8o".inp", "r")) { freopen(Y8o".inp", "r", stdin); // freopen(Y8o".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); } void ctime() { cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; } int n, S; pii st, en; char a[maxn][maxn]; int lim[maxn][maxn], dp[maxn][maxn]; int dx[] = { 1, -1, 0, 0 }; int dy[] = { 0, 0, -1, 1 }; bool exist(int u, int v) { return 1 <= u && u <= n && 1 <= v && v <= n && a[u][v] != 'T'; } bool check(int tg) { for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) dp[i][j] = 1e9; dp[st.f][st.s] = tg * S; queue<pii> q; q.push(st); while(q.size()) { int i, j; tie(i, j) = q.front(); q.pop(); for(int t = 0; t <= 3; t ++) { int u = i + dx[t], v = j + dy[t]; if(exist(u, v) && dp[i][j] + 1 < lim[u][v]) { dp[u][v] = dp[i][j] + 1; q.push({ u, v }); } } } return dp[en.f][en.s] < lim[en.f][en.s]; } void solve() { cin >> n >> S; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { cin >> a[i][j]; if(a[i][j] == 'M') st = {i, j}; else if(a[i][j] == 'D') en = {i, j}; } queue<pii> q; for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { lim[i][j] = 1e9; if(a[i][j] == 'H') lim[i][j] = 0, q.push({ i, j }); } while(q.size()) { int i, j; tie(i, j) = q.front(); q.pop(); for(int t = 0; t <= 3; t ++) { int u = i + dx[t], v = j + dy[t]; if(exist(u, v)) { if(lim[u][v] > lim[i][j] + S) { lim[u][v] = lim[i][j] + S; q.push({ u, v }); } } } } int l = 1, r = n * n; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) l = mid + 1; else r = mid - 1; } cout << r; } int main() { iof(); int nTest = 1; // cin >> nTest; while(nTest --) { solve(); } ctime(); return 0; }

Compilation message (stderr)

mecho.cpp: In function 'void iof()':
mecho.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(Y8o".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...