답안 #583174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
583174	2022-06-25T00:51:57 Z	HeyYouNotYouYou	Mecho (IOI09_mecho)	C++14	30 / 100	689 ms	16068 KB

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];
  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]=0;
  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

30.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	212 KB	Output isn't correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Incorrect	1 ms	212 KB	Output isn't correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Correct	0 ms	212 KB	Output is correct
6	Incorrect	1 ms	212 KB	Output isn't correct
7	Incorrect	473 ms	15552 KB	Output isn't correct
8	Incorrect	1 ms	340 KB	Output isn't 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	2 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	Correct	1 ms	340 KB	Output is correct
17	Incorrect	1 ms	340 KB	Output isn't correct
18	Correct	1 ms	340 KB	Output is correct
19	Incorrect	1 ms	340 KB	Output isn't correct
20	Correct	1 ms	340 KB	Output is correct
21	Incorrect	1 ms	468 KB	Output isn't correct
22	Correct	1 ms	468 KB	Output is correct
23	Incorrect	1 ms	468 KB	Output isn't correct
24	Correct	1 ms	468 KB	Output is correct
25	Incorrect	2 ms	596 KB	Output isn't correct
26	Correct	2 ms	596 KB	Output is correct
27	Incorrect	2 ms	596 KB	Output isn't correct
28	Correct	1 ms	596 KB	Output is correct
29	Incorrect	2 ms	596 KB	Output isn't correct
30	Correct	2 ms	596 KB	Output is correct
31	Incorrect	2 ms	724 KB	Output isn't correct
32	Correct	2 ms	724 KB	Output is correct
33	Incorrect	33 ms	4348 KB	Output isn't correct
34	Correct	36 ms	4392 KB	Output is correct
35	Correct	70 ms	4408 KB	Output is correct
36	Incorrect	56 ms	5188 KB	Output isn't correct
37	Correct	50 ms	5204 KB	Output is correct
38	Correct	86 ms	5304 KB	Output is correct
39	Incorrect	60 ms	6268 KB	Output isn't correct
40	Correct	68 ms	6400 KB	Output is correct
41	Correct	155 ms	6284 KB	Output is correct
42	Incorrect	75 ms	7252 KB	Output isn't correct
43	Correct	81 ms	7328 KB	Output is correct
44	Correct	151 ms	7356 KB	Output is correct
45	Incorrect	107 ms	8588 KB	Output isn't correct
46	Correct	94 ms	8464 KB	Output is correct
47	Correct	200 ms	8476 KB	Output is correct
48	Incorrect	141 ms	9672 KB	Output isn't correct
49	Correct	121 ms	9576 KB	Output is correct
50	Correct	209 ms	9684 KB	Output is correct
51	Incorrect	153 ms	10964 KB	Output isn't correct
52	Correct	146 ms	10868 KB	Output is correct
53	Correct	329 ms	10984 KB	Output is correct
54	Incorrect	180 ms	12340 KB	Output isn't correct
55	Correct	178 ms	12344 KB	Output is correct
56	Correct	470 ms	12356 KB	Output is correct
57	Incorrect	195 ms	13788 KB	Output isn't correct
58	Correct	195 ms	13776 KB	Output is correct
59	Correct	528 ms	13800 KB	Output is correct
60	Incorrect	232 ms	15228 KB	Output isn't correct
61	Correct	233 ms	15316 KB	Output is correct
62	Correct	532 ms	15384 KB	Output is correct
63	Correct	519 ms	15332 KB	Output is correct
64	Correct	642 ms	15332 KB	Output is correct
65	Correct	547 ms	15336 KB	Output is correct
66	Incorrect	629 ms	15332 KB	Output isn't correct
67	Correct	531 ms	15308 KB	Output is correct
68	Correct	631 ms	15392 KB	Output is correct
69	Correct	602 ms	15388 KB	Output is correct
70	Correct	568 ms	15388 KB	Output is correct
71	Correct	626 ms	15380 KB	Output is correct
72	Incorrect	521 ms	15384 KB	Output isn't correct
73	Incorrect	556 ms	15940 KB	Output isn't correct
74	Correct	575 ms	15948 KB	Output is correct
75	Correct	689 ms	15944 KB	Output is correct
76	Correct	595 ms	16068 KB	Output is correct
77	Correct	567 ms	15948 KB	Output is correct
78	Correct	515 ms	15848 KB	Output is correct
79	Correct	585 ms	15976 KB	Output is correct
80	Correct	543 ms	15960 KB	Output is correct
81	Correct	509 ms	15848 KB	Output is correct
82	Correct	514 ms	15948 KB	Output is correct
83	Correct	526 ms	15780 KB	Output is correct
84	Correct	526 ms	15888 KB	Output is correct
85	Correct	519 ms	15776 KB	Output is correct
86	Correct	473 ms	15764 KB	Output is correct
87	Correct	523 ms	15884 KB	Output is correct
88	Correct	483 ms	15664 KB	Output is correct
89	Correct	531 ms	15656 KB	Output is correct
90	Correct	494 ms	15660 KB	Output is correct
91	Correct	505 ms	15784 KB	Output is correct
92	Correct	506 ms	15656 KB	Output is correct