Submission #565644

#	Time	Username	Problem	Language	Result	Execution time	Memory
565644		Quan2003	Mecho (IOI09_mecho)	C++17	16 / 100	245 ms	15600 KiB

mecho

#include <bits/stdc++.h>
#include <iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int sz=1005;
int n,s;
int d1[sz][sz];
int d0[sz][sz];
bool vis1[sz][sz];
bool vis0[sz][sz];
vector<pair<int,int>>hiv;
int px,py;
int dx,dy;
ll step[sz][sz];
int movex[4]={0,0,1,-1};
int movey[4]={-1,1,0,0};
char c[sz][sz];
void bfs(vector<pair<int,int>>&a,int d[sz][sz],bool visited[sz][sz]){
    queue<pair<int,int>>q;
    for (auto i:a){
        q.push(i);
        visited[i.first][i.second]=1;
    }
    while (!q.empty()){
        int x1=q.front().first;
        int y1=q.front().second;
        q.pop();
        for (int i=0;i<4;i++){
            int x2=x1+movex[i];
            int y2=y1+movey[i];
            if (x2<0 or x2>=n) continue;
            if (y2<0 or y2>=n) continue;
            if (c[x2][y2]!='.' or visited[x2][y2]) continue;
                visited[x2][y2]=1;
                d[x2][y2]=d[x1][y1]+1;
                q.push({x2,y2}); 
        }
    } 
}
bool bsearch(int k){
    for (int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           vis1[i][j]=0;
           d1[i][j]=0;
           step[i][j]=LLONG_MAX;
       }
    }
    queue<pair<int,int>>q;
    q.push({px,py});
    step[px][py]=k;
    while (!q.empty()){
        int sx=q.front().first;
        int sy=q.front().second;
        q.pop();
        for (int i=0;i<4;i++){
            int tx=sx+movex[i];
            int ty=sy+movey[i];
            if (ty<0 or tx>=n) continue;
            if (ty<0 or ty>=n) continue;
            if (c[tx][ty]!='.' or vis1[tx][ty]) continue;
            d1[tx][ty]=d1[sx][sy]+1;
            int moves=k+d1[tx][ty]%s+1;
            if (moves>=d0[tx][ty]) continue;
            step[tx][ty]=moves;
            vis1[tx][ty]=1;
            q.push({tx,ty});
        }
    } for (int i=0;i<4;i++){
         int tx=dx+movex[i];
         int ty=dy+movey[i];
         if (tx<0 or tx>=n or ty<0 or ty>=n) continue;
         if (step[tx][ty]<d0[tx][ty]) return 1;
    } return 0;
}
int main(){
    cin>>n>>s;
    for (int i=0;i<n;i++){
        for(int j=0;j<n;j++){
             char y; cin>>y;
             c[i][j]=y;
             if (c[i][j]=='G'){
                 c[i][j]='.';
             }
             if (c[i][j]=='D'){
                 dx=i;dy=j;
                 c[i][j]='.';
             }
             if (c[i][j]=='M'){
                 px=i;py=j;
             } if (c[i][j]=='H'){
                 hiv.push_back({i,j});
             }
        }
    } bfs(hiv,d0,vis0);
      int low=0;int high=1e6;
      while (high>low){
          int mid=low+(high-low+1)/2;
          if (bsearch(mid)) low=mid;
          else high=mid-1;
      } 
        if (!bsearch(low)) cout <<-1;
        else cout <<low;
}

• Subtask 1: 16 / 100