Submission #583407

#	Time	Username	Problem	Language	Result	Execution time	Memory
583407		HeyYouNotYouYou	Mecho (IOI09_mecho)	C++14	30 / 100	745 ms	21716 KiB

mecho

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int n , o, srcx, srcy, destx, desty, ar[N][N];
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
struct node{
  int x, y, dist;
};
bool valid1(int x, int y){
  if(x>=0 && x<n && y>=0 && y<n && (x!=srcx || y!=srcy) && (x!=destx || y!=desty)) return true;
  return false;
}
bool valid(int x, int y){
  if(x>=0 && x<n && y>=0 && y<n) return true;
  return false;
}
bool check(int mins)
{
  vector<pair<int,int>>hives;
  int arr[n][n],arr2[n][n];
  for(int i = 0 ; i < n ; i ++)
    for(int j = 0 ; j < n ; j ++)
      {
        arr[i][j]=ar[i][j]; arr2[i][j]=1;
        if(arr[i][j]==1) hives.push_back({i,j});
      }
  queue<pair<int,int>>q;
  int vis[n][n];
  memset(vis,0,sizeof vis);
  for(auto e : hives){
    q.push({e.first,e.second});
    vis[e.first][e.second]=1;
  }
 
  while(!q.empty())
  {
    int curx=q.front().first;
    int cury=q.front().second;
    q.pop();
    for(int i = 0 ; i < 4; i ++)
    {
      int gox = curx+dx[i], goy = cury+dy[i];
      if(valid(gox,goy) && !vis[gox][goy] && !arr[gox][goy]){
        vis[gox][goy]=1;
        arr[gox][goy]=arr[curx][cury]+1;
        q.push({gox,goy});
      }
    }
  }
 
 queue<pair<pair<int,int>,int>>qq;
  memset(vis,0,sizeof vis);
  qq.push({{srcx,srcy},0});
  vis[srcx][srcy]=1;
  if(arr[srcx][srcy]<=mins) return false;
  arr[srcx][srcy]=1;
  while(!qq.empty()){
    int curx=qq.front().first.first;
    int cury=qq.front().first.second;
    int c = qq.front().second;
    if(curx==destx&&cury==desty) return true;
    qq.pop();
    for(int i = 0 ; i < 4; i ++)
    {
      int gox = curx+dx[i], goy = cury+dy[i];
 
      if(valid(gox,goy) && !vis[gox][goy] && arr[gox][goy]!=-1){
 
        if(mins+arr2[curx][cury]+(c%o==0&&c>0) < arr[gox][goy]){
          vis[gox][goy]=1;
          if(c%o!=0||!c)
          arr2[gox][goy]=arr2[curx][cury];
          else
          arr2[gox][goy]=arr2[curx][cury]+1;
          qq.push({{gox,goy},c+1});
        }
      }
    }
  }
 
 
  return false;
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n >> o;
  int id[n][n];
  for(int i = 0 ; i < n ; i ++){
    for(int j = 0 ; j < n ; j ++){
      char x; cin >> x;
      ar[i][j] = (x=='H'?1:((x=='G'||x=='D'||x=='M')?0:-1));
      if(x=='M') srcx=i, srcy=j;
      if(x=='D') destx=i, desty=j;
    }
  }
  int l = 0 , r = n*n;
  int ans=-1;
  while(l <= r)
  {
    int mid = (l+r)/2;
    if(check(mid))
    {
      l = mid+1;
      ans=mid;
    }
    else
    {
      r = mid-1;
    }
  }
  cout<<ans<<endl;
}

Compilation message (stderr)

mecho.cpp: In function 'int32_t main()':
mecho.cpp:91:7: warning: unused variable 'id' [-Wunused-variable]
   91 |   int id[n][n];
      |       ^~

• Subtask 1: 30 / 100