Submission #969610

#TimeUsernameProblemLanguageResultExecution timeMemory
969610rahidilbayramliMecho (IOI09_mecho)C++17
100 / 100
140 ms12684 KiB
#pragma GCC optimize("-O3") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define vl vector<ll> #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define p_b pop_back #define f first #define s second using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const ll sz = 850; char grid[sz][sz]; ll dist[sz][sz], ch[sz][sz], n, s, i, j, k; ll dx[] = {0, 1, 0, -1}; ll dy[] = {1, 0, -1, 0}; pll st, en; ll bfs(ll mid) { if(dist[st.f][st.s] - mid * s <= 0) return 0; for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) ch[i][j] = 0; } queue<pll>q; q.push(st); while(!q.empty()) { pll node = q.front(); q.pop(); for(k = 0; k < 4; k++) { pll nnode = {node.f + dx[k], node.s + dy[k]}; if(nnode.f >= 1 && nnode.f <= n && nnode.s >= 1 && nnode.s <= n) { if(ch[nnode.f][nnode.s] == 0 && grid[nnode.f][nnode.s] != 'T' && grid[nnode.f][nnode.s] != 'M' && dist[nnode.f][nnode.s] - mid * s > ch[node.f][node.s] + 1) { ch[nnode.f][nnode.s] = ch[node.f][node.s] + 1; q.push(nnode); } } } } if(ch[en.f][en.s] > 0) return 1; return 0; } void solve() { cin >> n >> s; queue<pll>q; for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++){ cin >> grid[i][j]; if(grid[i][j] == 'M') st = {i, j}; else if(grid[i][j] == 'D') en = {i, j}; else if(grid[i][j] == 'H') q.push({i, j}); } } while(!q.empty()) { pll node = q.front(); q.pop(); for(k = 0; k < 4; k++) { pll nnode = {node.f + dx[k], node.s + dy[k]}; if(nnode.f >= 1 && nnode.f <= n && nnode.s >= 1 && nnode.s <= n) { if(dist[nnode.f][nnode.s] == 0 && grid[nnode.f][nnode.s] != 'H' && grid[nnode.f][nnode.s] != 'T' && grid[nnode.f][nnode.s] != 'D') { dist[nnode.f][nnode.s] = dist[node.f][node.s] + s; q.push(nnode); } } } } dist[en.f][en.s] = LLONG_MAX; ll l = 0, r = 1000000000, ans = -1; while(l <= r) { ll mid = (l + r) / 2; if(bfs(mid)) { ans = max(ans, mid); l = mid + 1; } else r = mid - 1; } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll tests = 1; //cin >> tests; while(tests--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...