oj.uz

답안 #583176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583176 2022-06-25T00:53:23 Z HeyYouNotYouYou Mecho (IOI09_mecho) C++14
8 / 100
 641 ms 16116 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+1) <= 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 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 1 ms 212 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Correct 500 ms 15548 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 292 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 2 ms 596 KB Output isn't correct
13 Incorrect 1 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 1 ms 468 KB Output isn't correct
24 Incorrect 2 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 1 ms 596 KB Output isn't correct
28 Incorrect 2 ms 596 KB Output isn't correct
29 Incorrect 2 ms 596 KB Output isn't correct
30 Incorrect 2 ms 596 KB Output isn't correct
31 Incorrect 2 ms 724 KB Output isn't correct
32 Incorrect 3 ms 732 KB Output isn't correct
33 Incorrect 35 ms 4404 KB Output isn't correct
34 Incorrect 38 ms 4308 KB Output isn't correct
35 Incorrect 62 ms 4400 KB Output isn't correct
36 Incorrect 50 ms 5300 KB Output isn't correct
37 Incorrect 50 ms 5288 KB Output isn't correct
38 Incorrect 103 ms 5300 KB Output isn't correct
39 Incorrect 95 ms 6268 KB Output isn't correct
40 Incorrect 59 ms 6272 KB Output isn't correct
41 Incorrect 111 ms 6284 KB Output isn't correct
42 Incorrect 83 ms 7340 KB Output isn't correct
43 Incorrect 93 ms 7328 KB Output isn't correct
44 Incorrect 141 ms 7332 KB Output isn't correct
45 Incorrect 119 ms 8464 KB Output isn't correct
46 Incorrect 107 ms 8456 KB Output isn't correct
47 Incorrect 222 ms 8480 KB Output isn't correct
48 Incorrect 123 ms 9684 KB Output isn't correct
49 Incorrect 131 ms 9684 KB Output isn't correct
50 Incorrect 241 ms 9688 KB Output isn't correct
51 Incorrect 144 ms 10968 KB Output isn't correct
52 Incorrect 176 ms 11044 KB Output isn't correct
53 Incorrect 334 ms 11012 KB Output isn't correct
54 Incorrect 180 ms 12352 KB Output isn't correct
55 Incorrect 169 ms 12344 KB Output isn't correct
56 Incorrect 344 ms 12292 KB Output isn't correct
57 Incorrect 189 ms 13792 KB Output isn't correct
58 Incorrect 187 ms 13728 KB Output isn't correct
59 Incorrect 439 ms 13800 KB Output isn't correct
60 Incorrect 214 ms 15312 KB Output isn't correct
61 Incorrect 211 ms 15316 KB Output isn't correct
62 Incorrect 513 ms 15328 KB Output isn't correct
63 Incorrect 506 ms 15336 KB Output isn't correct
64 Incorrect 538 ms 15384 KB Output isn't correct
65 Incorrect 545 ms 15336 KB Output isn't correct
66 Incorrect 560 ms 15360 KB Output isn't correct
67 Correct 506 ms 15460 KB Output is correct
68 Incorrect 524 ms 15308 KB Output isn't correct
69 Incorrect 570 ms 15508 KB Output isn't correct
70 Incorrect 524 ms 15484 KB Output isn't correct
71 Incorrect 521 ms 15420 KB Output isn't correct
72 Incorrect 546 ms 15384 KB Output isn't correct
73 Incorrect 546 ms 15976 KB Output isn't correct
74 Incorrect 598 ms 16116 KB Output isn't correct
75 Incorrect 641 ms 15940 KB Output isn't correct
76 Incorrect 605 ms 15988 KB Output isn't correct
77 Incorrect 621 ms 16000 KB Output isn't correct
78 Correct 544 ms 15876 KB Output is correct
79 Incorrect 518 ms 15904 KB Output isn't correct
80 Incorrect 525 ms 15852 KB Output isn't correct
81 Incorrect 562 ms 15820 KB Output isn't correct
82 Incorrect 474 ms 15856 KB Output isn't correct
83 Incorrect 478 ms 15772 KB Output isn't correct
84 Incorrect 493 ms 15776 KB Output isn't correct
85 Incorrect 505 ms 15776 KB Output isn't correct
86 Incorrect 481 ms 15800 KB Output isn't correct
87 Incorrect 499 ms 15792 KB Output isn't correct
88 Incorrect 479 ms 15684 KB Output isn't correct
89 Incorrect 503 ms 15764 KB Output isn't correct
90 Incorrect 471 ms 15916 KB Output isn't correct
91 Incorrect 491 ms 15772 KB Output isn't correct
92 Incorrect 525 ms 15656 KB Output isn't correct