oj.uz

Submission #583475

# Submission time Handle Problem Language Result Execution time Memory
583475 2022-06-25T11:49:09 Z HeyYouNotYouYou Mecho (IOI09_mecho) C++14
24 / 100
 839 ms 21128 KB 
#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];
  queue<pair<int,int>>q;
  int vis[n][n];
  memset(vis,0,sizeof vis);
  for(int i = 0 ; i < n ; i ++)
    for(int j = 0 ; j < n ; j ++)
      {
        if(ar[i][j]==1){
          q.push({i,j});
          vis[i][j]=1;
          arr[i][j]=0;
        }
      }
 
  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] && ar[gox][goy]!=-1 && (destx!=gox || desty!=goy)){
        vis[gox][goy]=1;
        arr[gox][goy]=arr[curx][cury]+1;
        q.push({gox,goy});
      }
    }
  }
 
 queue<pair<int,int>>qq;
  memset(vis,0,sizeof vis);
  memset(arr2,0,sizeof arr2);
  qq.push({srcx,srcy});
  vis[srcx][srcy]=1;
  if(arr[srcx][srcy]<=mins) return false;
  arr2[srcx][srcy]=0;
  while(!qq.empty()){
    int curx=qq.front().first;
    int cury=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] && ar[gox][goy]!=-1){
        if(arr[gox][goy] > floor((double)(arr2[curx][cury]+1)/(double)o)+mins){
        //  cout<<curx<<" "<<cury<<" "<<gox<<" "<<goy<<" "<<arr2[curx][cury]<<" "<<arr[gox][goy]-mins<<" "<<c<<" "<<arr2[curx][cury]+(c%o==0&&c>0)<<endl;
          vis[gox][goy]=1;
          arr2[gox][goy]=arr2[curx][cury]+1;
          qq.push({gox,goy});
        }
      }
    }
  }
 
 
  return false;
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n >> o;
  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;
  //  cout<<mid<<endl;
    if(check(mid))
    {
      l = mid+1;
      ans=mid;
    }
    else
    {
      r = mid-1;
    }
  }
  cout<<ans<<endl;
}

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Correct 0 ms 340 KB Output is correct
7 Incorrect 535 ms 20548 KB Output isn't correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 1 ms 596 KB Output isn't correct
13 Incorrect 2 ms 468 KB Output isn't correct
14 Correct 3 ms 596 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Incorrect 1 ms 340 KB Output isn't correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 Incorrect 1 ms 340 KB Output isn't correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Incorrect 1 ms 468 KB Output isn't correct
22 Incorrect 1 ms 468 KB Output isn't correct
23 Incorrect 1 ms 468 KB Output isn't correct
24 Incorrect 1 ms 468 KB Output isn't correct
25 Incorrect 2 ms 596 KB Output isn't correct
26 Incorrect 2 ms 596 KB Output isn't correct
27 Incorrect 2 ms 596 KB Output isn't correct
28 Incorrect 3 ms 596 KB Output isn't correct
29 Incorrect 2 ms 700 KB Output isn't correct
30 Incorrect 3 ms 724 KB Output isn't correct
31 Incorrect 3 ms 724 KB Output isn't correct
32 Incorrect 3 ms 724 KB Output isn't correct
33 Incorrect 57 ms 5344 KB Output isn't correct
34 Incorrect 59 ms 5332 KB Output isn't correct
35 Correct 87 ms 5352 KB Output is correct
36 Incorrect 75 ms 6544 KB Output isn't correct
37 Incorrect 88 ms 6484 KB Output isn't correct
38 Correct 96 ms 6604 KB Output is correct
39 Incorrect 97 ms 7856 KB Output isn't correct
40 Incorrect 105 ms 7860 KB Output isn't correct
41 Correct 121 ms 7868 KB Output is correct
42 Incorrect 125 ms 9300 KB Output isn't correct
43 Incorrect 141 ms 9280 KB Output isn't correct
44 Correct 154 ms 9300 KB Output is correct
45 Incorrect 143 ms 10836 KB Output isn't correct
46 Incorrect 190 ms 10836 KB Output isn't correct
47 Correct 218 ms 10884 KB Output is correct
48 Incorrect 171 ms 12500 KB Output isn't correct
49 Incorrect 229 ms 12496 KB Output isn't correct
50 Correct 290 ms 12508 KB Output is correct
51 Incorrect 196 ms 14272 KB Output isn't correct
52 Incorrect 245 ms 14272 KB Output isn't correct
53 Correct 392 ms 14292 KB Output is correct
54 Incorrect 243 ms 16176 KB Output isn't correct
55 Incorrect 329 ms 16180 KB Output isn't correct
56 Correct 434 ms 16188 KB Output is correct
57 Incorrect 314 ms 18184 KB Output isn't correct
58 Incorrect 342 ms 18220 KB Output isn't correct
59 Correct 571 ms 18200 KB Output is correct
60 Incorrect 321 ms 20232 KB Output isn't correct
61 Incorrect 394 ms 20328 KB Output isn't correct
62 Correct 599 ms 20344 KB Output is correct
63 Correct 646 ms 20332 KB Output is correct
64 Correct 722 ms 20332 KB Output is correct
65 Correct 662 ms 20364 KB Output is correct
66 Correct 654 ms 20324 KB Output is correct
67 Correct 587 ms 20336 KB Output is correct
68 Correct 627 ms 20384 KB Output is correct
69 Correct 707 ms 20388 KB Output is correct
70 Correct 579 ms 20388 KB Output is correct
71 Correct 651 ms 20504 KB Output is correct
72 Correct 601 ms 20388 KB Output is correct
73 Incorrect 646 ms 21028 KB Output isn't correct
74 Incorrect 779 ms 21128 KB Output isn't correct
75 Incorrect 753 ms 20880 KB Output isn't correct
76 Incorrect 805 ms 20920 KB Output isn't correct
77 Incorrect 732 ms 20896 KB Output isn't correct
78 Correct 637 ms 20944 KB Output is correct
79 Incorrect 653 ms 21000 KB Output isn't correct
80 Incorrect 618 ms 20876 KB Output isn't correct
81 Incorrect 625 ms 20856 KB Output isn't correct
82 Incorrect 657 ms 20828 KB Output isn't correct
83 Incorrect 679 ms 20756 KB Output isn't correct
84 Incorrect 684 ms 20652 KB Output isn't correct
85 Incorrect 839 ms 20748 KB Output isn't correct
86 Incorrect 685 ms 20720 KB Output isn't correct
87 Incorrect 732 ms 20796 KB Output isn't correct
88 Incorrect 643 ms 20644 KB Output isn't correct
89 Incorrect 759 ms 20724 KB Output isn't correct
90 Incorrect 752 ms 20648 KB Output isn't correct
91 Incorrect 809 ms 20644 KB Output isn't correct
92 Incorrect 659 ms 20652 KB Output isn't correct