Submission #698906

#	Time	Username	Problem	Language	Result	Execution time	Memory
698906		aedmhsn	Mecho (IOI09_mecho)	C++17	17 / 100	196 ms	6900 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];
int dist[2][mxN][mxN];
bool during[mxN][mxN];

queue <pii> q;
vector <pii> 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) && 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(int 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[1][u.A][u.B]+1)%s != 0) <= dist[0][u.A+x][u.B+y]-rest){
                dist[1][u.A+x][u.B+y] = dist[1][u.A][u.B]+1;
                if(during[u.A][u.B] && (dist[1][u.A][u.B]+1)%s == 0){
                    continue;
                }
                if(during[u.A][u.B]){
                    during[u.A+x][u.B+y]=1;
                }
                q.push({u.A+x, u.B+y});
                if((dist[1][u.A][u.B]+1)%s != 0 && (dist[1][u.A][u.B]+1)/s + 1 == dist[0][u.A+x][u.B+y]-rest){
                    during[u.A+x][u.B+y]=1;
                }
            }
        }
    }
}

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};
        }
    }
    int st=0, en=1e9, mid, ans=-1;
    bfs();
    while(st<=en){
        mid = (st+en)/2;
        q.push(ip);
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dist[1][i][j]=-1;
                during[i][j]=0;
            }
        }
        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 << dist[1][4][4] << " " << dist[0][4][4];
    cout << ans;
}

• Subtask 1: 17 / 100