Submission #698915

#	Time	Username	Problem	Language	Result	Execution time	Memory
698915		aedmhsn	Mecho (IOI09_mecho)	C++17	84 / 100	206 ms	11636 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
 
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

const int mxN=805;

char grid[mxN][mxN];
ll dist[2][mxN][mxN];

queue <pll> q;
vector <pll> moves={{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

int n, s;
bool valid(int i, int j){
    if(i >= 1 && i <= n && j >= 1 && j <= n && grid[i][j] != 'H' && grid[i][j] != 'T')
        return true;
    return false;
}



void bfs(){
    while(!q.empty()){
        pii u = q.front();
        q.pop();
        for(auto [x, y]:moves){
            if(valid(u.A+x, u.B+y) && grid[u.A+x][u.B+y] != 'D' && grid[u.A+x][u.B+y]!= 'M' && dist[0][u.A+x][u.B+y] == -1){
                dist[0][u.A+x][u.B+y] = dist[0][u.A][u.B]+1;
                q.push({u.A+x, u.B+y});
            }
        }
    }
}
void bfs2(ll rest){
    while(!q.empty()){
        pii u = q.front();
        q.pop();
        for(auto [x,y]:moves){
            if(valid(u.A+x, u.B+y) && dist[1][u.A+x][u.B+y] == -1 && (dist[1][u.A][u.B]+1)/s < dist[0][u.A+x][u.B+y]-rest){
                dist[1][u.A+x][u.B+y] = dist[1][u.A][u.B]+1;
                q.push({u.A+x, u.B+y});
            }
        }
    }
}

int main(){
    ms(dist, -1);
    cin >> n >> s;
    pii ip, ep;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> grid[i][j];
            if(grid[i][j] == 'H'){
                q.push({i, j});
                dist[0][i][j]=0;
            }
            else if(grid[i][j] == 'M')
                ip={i, j};
            else if(grid[i][j] == 'D')
                ep={i, j};
        }
    }
    ll st=0, en=1e9, mid, ans=-1;
    bfs();
    dist[0][ep.A][ep.B] = INT_MAX;
    while(st<=en){
        mid = (st+en)/2;
        q.push(ip);
        ms(dist[1], -1);
        dist[1][ip.A][ip.B]=0;
        bfs2(mid);
        if(dist[1][ep.A][ep.B] != -1){
            ans = mid;
            st = mid+1;
        }
        else
            en = mid-1;
    }
    cout << ans;
}

• Subtask 1: 84 / 100