제출 #1083698

#제출 시각아이디문제언어결과실행 시간메모리
1083698hohemheinMecho (IOI09_mecho)C++17
100 / 100
128 ms7840 KiB
#include <bits/stdc++.h> #define ii pair<int,int> #define iii pair<ii,int> #define iiii pair<ii,ii> #define f first #define s second #define pb push_back #define pu push #define ll long long #define int long long #define endl "\n" #define all(x) (x).begin() , (x).end() using namespace std; const int nmax = 8e2+4; const int oo = 1e12+3; const ll mod = 1e9+7; char m[nmax][nmax]; int bee[nmax][nmax]; bool bear[nmax][nmax]; int mov[] = { 1,-1 }; void llenar(){ for( int i = 0; i < nmax; i++ ){ fill( bee[i], bee[i]+nmax, oo); } } void bfsBee( vector<ii>&aux, int n ){ queue<ii>c; for( auto [i,j] : aux ){ c.pu({i,j}); bee[i][j] = 0; } while( !c.empty() ){ auto [x,y] = c.front(); c.pop(); for( int i = 0; i < 2; i++ ) if( x+mov[i] > 0 && x+mov[i] <= n && m[ x+mov[i] ][y] == 'G' && bee[ x+mov[i] ][y] == oo ){ c.pu( {x+mov[i],y} ); bee[ x+mov[i] ][y] = bee[x][y]+1; } for( int i = 0; i < 2; i++ ) if( y+mov[i] > 0 && y+mov[i] <= n && m[x][y+mov[i]] == 'G' && bee[x][y+mov[i]] == oo ){ c.pu( {x,y+mov[i]} ); bee[x][y+mov[i]] = bee[x][y]+1; } } } void bfsBear( ii X, int n, int k, int op ){ for( int i = 0; i <= n+1; i++ ){ fill( bear[i], bear[i]+n+2, false ); } queue<iiii>c; bear[X.f][X.s] = true; c.pu({ X, {op,1} }); while( !c.empty() ){ auto [x,y] = c.front().f; auto add = c.front().s.s; auto pe = c.front().s.f + ( ( (add%k) == 0)?1:0 ); c.pop(); for( int i = 0; i < 2; i++ ){ if( x+mov[i] > 0 && x+mov[i] <= n && m[ x+mov[i] ][y] != 'T' && !bear[ x+mov[i] ][y] && bee[ x+mov[i] ][y] > pe ){ c.pu( { {x+mov[i],y} , {pe,add+1} } ); bear[ x+mov[i] ][y] = true; } } for( int i = 0; i < 2; i++ ){ if( y+mov[i] > 0 && y+mov[i] <= n && m[x][y+mov[i]] != 'T'&& !bear[x][y+mov[i]] && bee[x][y+mov[i]] > pe ){ c.pu( { {x,y+mov[i]}, {pe,add+1} } ); bear[x][y+mov[i]] = true; } } } } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(); //cout << fixed << setprecision(4); /*ifstream cin ("atlarge.in"); ofstream cout ("atlarge.out");*/ llenar(); int n, k; cin >> n >> k; ii init, meta; vector<ii>aux; for( int i = 1; i <= n; i++ ) for( int j = 1; j <= n; j++ ){ cin >> m[i][j]; if( m[i][j] == 'H' )aux.pb({i,j}); else if( m[i][j] == 'M' )init = {i,j}; else if( m[i][j] == 'D' )meta = {i,j}; } m[init.f][init.s] = 'G'; bfsBee( aux, n ); int l = 0,r = bee[init.f][init.s]; while( r-l > 1 ){ int m = (r+l)>>1; bfsBear( init, n, k,m); if( bear[meta.f][meta.s] )l = m; else r = m; /* cout << m <<"\n"; for( int i = 1; i <= n; i++ ){ for( int j = 1; j <= n; j++ ) cout << bear[i][j] <<" "; cout <<"\n"; } cout << "\n\n";*/ } bfsBear( init, n, k, l); cout << ( ( bear[meta.f][meta.s] )? l : -1 ) <<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...