제출 #712041

#제출 시각아이디문제언어결과실행 시간메모리
712041NarkaMecho (IOI09_mecho)C++14
38 / 100
181 ms6028 KiB
#include<bits/stdc++.h> using namespace std ; # define F first # define S second # define int long long # define in insert # define pb push_back # define pob pop_back # define INF INT_MAX # define INFL 1e18 + 10 # define mod 1000000007 # define vi vector<int> # define pii pair<int , int> # define vvi vector< vector<int> > # define vpi vector<pair<int, int>> # define all(v) v.begin() , v.end() # define debug(x) cerr << '\n' << #x << " = " << x << '\n' ; # define rep( i , s , e ) for( int i = s ; i <= e ; i++ ) # define repR( i , e , s ) for( int i = e ; i >= s ; i-- ) # define FAST ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); # define endl "\n" int mp[801][801]; vector<array<int, 2>> hives; int st[2], nd[2]; int n, s; queue<array<int, 2>> q; bool safe(int i, int j){ if(mp[i][j] == -2) return false; if(j < n && j >= 0 && i < n && i >= 0) return true; return false; } int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; void attack(){ for(auto x : hives){ q.push(x); } while(!q.empty()){ array<int, 2> t = q.front(); q.pop(); rep(i, 0, 3){ int x = t[0] + dx[i]; int y = t[1] + dy[i]; if(safe(x, y)){ if(mp[x][y] == 0) mp[x][y] = mp[t[0]][t[1]] + 1, q.push({x, y}); } } } } bool is_can(int v){ vector<vector<bool>> vis(805, vector<bool>(805, false)); q.push({st[0], st[1]}); if(mp[st[0]][st[1]] <= v) return false; vis[st[0]][st[1]] = true; int t = 1, b = 0, stp = 1, c = 0; while(!q.empty()){ array<int, 2> tt = q.front(); q.pop(), t--; rep(i, 0, 3){ int x = tt[0] + dx[i]; int y = tt[1] + dy[i]; if(x == nd[0] && y == nd[1]) return true; if(safe(x, y)&& !vis[x][y] && stp + v < mp[x][y] ){ b++; q.push({x, y}); vis[x][y] = true; } } if(t == 0){ t = b; c++; b = 0; } if(c == s){ c = 0; stp++; } } return false; } void solve(){ cin >> n >> s; rep(i, 0, n-1){ string a; cin >> a; rep(j, 0, n-1){ if(a[j] == 'T') mp[i][j] = -2; else if(a[j] == 'M') st[0] = i, st[1] = j; else if(a[j] == 'H') mp[i][j] = 1, hives.pb({i, j}); else if(a[j] == 'D') nd[0] = i, nd[1] = j; } } attack(); int l = 0, r = 1e9, res = INF; while(l <= r){ int md = (l+r)>>1; queue<array<int, 2>> empty; swap( q, empty ); if(is_can(md)){ res = md; l = md+1; }else{ r = md-1; } } if(res == INF) cout << -1 << endl; else cout << res << endl; } signed main(){ solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...