oj.uz

Submission #583177

# Submission time Handle Problem Language Result Execution time Memory
583177 2022-06-25T00:58:45 Z HeyYouNotYouYou Mecho (IOI09_mecho) C++14
8 / 100
 600 ms 16188 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];
  for(int i = 0 ; i < n ; i ++)
    for(int j = 0 ; j < n ; j ++)
      {
        arr[i][j]=ar[i][j];
        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});
      }
    }
  }

  memset(vis,0,sizeof vis);
  q.push({srcx,srcy});
  vis[srcx][srcy]=1;
  if(arr[srcx][srcy]<=mins) return false;
  arr[srcx][srcy]=1;
  while(!q.empty()){
    int curx=q.front().first;
    int cury=q.front().second;
    if(curx==destx&&cury==desty) return true;
    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]!=-1){
        if(((arr[curx][cury])/o) < arr[gox][goy] - mins){

          vis[gox][goy]=1;
          arr[gox][goy]=arr[curx][cury]+1;
          q.push({gox,goy});
        }
      }
    }
  }


  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

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

Subtask #1
8.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Correct 502 ms 15564 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Incorrect 1 ms 596 KB Output isn't correct
13 Incorrect 2 ms 468 KB Output isn't correct
14 Correct 2 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 2 ms 468 KB Output isn't correct
24 Incorrect 1 ms 468 KB Output isn't correct
25 Incorrect 1 ms 596 KB Output isn't correct
26 Incorrect 1 ms 596 KB Output isn't correct
27 Incorrect 2 ms 596 KB Output isn't correct
28 Incorrect 1 ms 596 KB Output isn't correct
29 Incorrect 2 ms 596 KB Output isn't correct
30 Incorrect 1 ms 596 KB Output isn't correct
31 Incorrect 2 ms 724 KB Output isn't correct
32 Incorrect 3 ms 724 KB Output isn't correct
33 Incorrect 33 ms 4308 KB Output isn't correct
34 Incorrect 34 ms 4308 KB Output isn't correct
35 Incorrect 59 ms 4400 KB Output isn't correct
36 Incorrect 49 ms 5292 KB Output isn't correct
37 Incorrect 51 ms 5244 KB Output isn't correct
38 Incorrect 102 ms 5296 KB Output isn't correct
39 Incorrect 61 ms 6268 KB Output isn't correct
40 Incorrect 57 ms 6228 KB Output isn't correct
41 Incorrect 103 ms 6304 KB Output isn't correct
42 Incorrect 76 ms 7328 KB Output isn't correct
43 Incorrect 87 ms 7252 KB Output isn't correct
44 Incorrect 141 ms 7344 KB Output isn't correct
45 Incorrect 106 ms 8404 KB Output isn't correct
46 Incorrect 93 ms 8464 KB Output isn't correct
47 Incorrect 227 ms 8472 KB Output isn't correct
48 Incorrect 128 ms 9676 KB Output isn't correct
49 Incorrect 118 ms 9696 KB Output isn't correct
50 Incorrect 211 ms 9668 KB Output isn't correct
51 Incorrect 155 ms 10968 KB Output isn't correct
52 Incorrect 136 ms 10880 KB Output isn't correct
53 Incorrect 260 ms 10980 KB Output isn't correct
54 Incorrect 176 ms 12244 KB Output isn't correct
55 Incorrect 171 ms 12256 KB Output isn't correct
56 Incorrect 376 ms 12352 KB Output isn't correct
57 Incorrect 200 ms 13884 KB Output isn't correct
58 Incorrect 189 ms 13784 KB Output isn't correct
59 Incorrect 456 ms 13800 KB Output isn't correct
60 Incorrect 216 ms 15356 KB Output isn't correct
61 Incorrect 227 ms 15356 KB Output isn't correct
62 Incorrect 497 ms 15436 KB Output isn't correct
63 Incorrect 522 ms 15336 KB Output isn't correct
64 Incorrect 550 ms 15328 KB Output isn't correct
65 Incorrect 564 ms 15244 KB Output isn't correct
66 Incorrect 561 ms 15336 KB Output isn't correct
67 Correct 520 ms 15308 KB Output is correct
68 Incorrect 542 ms 15384 KB Output isn't correct
69 Incorrect 581 ms 15452 KB Output isn't correct
70 Incorrect 541 ms 15392 KB Output isn't correct
71 Incorrect 506 ms 15332 KB Output isn't correct
72 Incorrect 531 ms 15512 KB Output isn't correct
73 Incorrect 555 ms 16188 KB Output isn't correct
74 Incorrect 591 ms 16040 KB Output isn't correct
75 Incorrect 576 ms 16136 KB Output isn't correct
76 Incorrect 570 ms 15948 KB Output isn't correct
77 Incorrect 600 ms 16100 KB Output isn't correct
78 Correct 525 ms 15988 KB Output is correct
79 Incorrect 554 ms 15852 KB Output isn't correct
80 Incorrect 515 ms 16000 KB Output isn't correct
81 Incorrect 573 ms 15908 KB Output isn't correct
82 Incorrect 508 ms 15948 KB Output isn't correct
83 Incorrect 505 ms 15860 KB Output isn't correct
84 Incorrect 554 ms 15776 KB Output isn't correct
85 Incorrect 528 ms 15772 KB Output isn't correct
86 Incorrect 536 ms 15776 KB Output isn't correct
87 Incorrect 479 ms 15752 KB Output isn't correct
88 Incorrect 497 ms 15660 KB Output isn't correct
89 Incorrect 477 ms 15728 KB Output isn't correct
90 Incorrect 469 ms 15628 KB Output isn't correct
91 Incorrect 524 ms 15656 KB Output isn't correct
92 Incorrect 521 ms 15652 KB Output isn't correct