Submission #583173

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583173	2022-06-25T00:19:56 Z	HeyYouNotYouYou	Mecho (IOI09_mecho)	C++14	73 / 100	646 ms	21180 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],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},1});
  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

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

Subtask #1

73.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	0 ms	212 KB	Output isn't correct
3	Correct	0 ms	212 KB	Output is correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Correct	1 ms	212 KB	Output is correct
6	Incorrect	1 ms	340 KB	Output isn't correct
7	Incorrect	481 ms	20600 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	1 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	1 ms	468 KB	Output isn't correct
14	Correct	2 ms	596 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	468 KB	Output is correct
22	Correct	1 ms	468 KB	Output is correct
23	Correct	1 ms	468 KB	Output is correct
24	Correct	1 ms	468 KB	Output is correct
25	Correct	1 ms	596 KB	Output is correct
26	Correct	1 ms	596 KB	Output is correct
27	Correct	2 ms	596 KB	Output is correct
28	Correct	2 ms	596 KB	Output is correct
29	Correct	2 ms	724 KB	Output is correct
30	Correct	2 ms	724 KB	Output is correct
31	Correct	2 ms	724 KB	Output is correct
32	Correct	2 ms	724 KB	Output is correct
33	Correct	37 ms	5356 KB	Output is correct
34	Correct	36 ms	5332 KB	Output is correct
35	Correct	63 ms	5376 KB	Output is correct
36	Correct	46 ms	6544 KB	Output is correct
37	Correct	51 ms	6484 KB	Output is correct
38	Correct	99 ms	6568 KB	Output is correct
39	Correct	67 ms	7868 KB	Output is correct
40	Correct	63 ms	7848 KB	Output is correct
41	Correct	119 ms	7868 KB	Output is correct
42	Correct	81 ms	9300 KB	Output is correct
43	Correct	85 ms	9304 KB	Output is correct
44	Correct	155 ms	9316 KB	Output is correct
45	Correct	101 ms	10948 KB	Output is correct
46	Correct	98 ms	10768 KB	Output is correct
47	Correct	202 ms	10944 KB	Output is correct
48	Correct	117 ms	12504 KB	Output is correct
49	Correct	124 ms	12496 KB	Output is correct
50	Correct	234 ms	12532 KB	Output is correct
51	Correct	146 ms	14276 KB	Output is correct
52	Correct	147 ms	14276 KB	Output is correct
53	Correct	291 ms	14284 KB	Output is correct
54	Correct	167 ms	16204 KB	Output is correct
55	Correct	174 ms	16072 KB	Output is correct
56	Correct	373 ms	16316 KB	Output is correct
57	Correct	186 ms	18284 KB	Output is correct
58	Correct	191 ms	18316 KB	Output is correct
59	Correct	454 ms	18344 KB	Output is correct
60	Correct	218 ms	20272 KB	Output is correct
61	Correct	217 ms	20428 KB	Output is correct
62	Correct	526 ms	20352 KB	Output is correct
63	Correct	529 ms	20464 KB	Output is correct
64	Correct	646 ms	20364 KB	Output is correct
65	Correct	566 ms	20464 KB	Output is correct
66	Correct	555 ms	20476 KB	Output is correct
67	Correct	540 ms	20356 KB	Output is correct
68	Correct	548 ms	20556 KB	Output is correct
69	Correct	576 ms	20516 KB	Output is correct
70	Correct	517 ms	20524 KB	Output is correct
71	Correct	631 ms	20524 KB	Output is correct
72	Incorrect	528 ms	20428 KB	Output isn't correct
73	Incorrect	532 ms	20956 KB	Output isn't correct
74	Correct	617 ms	21180 KB	Output is correct
75	Correct	606 ms	20948 KB	Output is correct
76	Correct	554 ms	20956 KB	Output is correct
77	Correct	571 ms	20956 KB	Output is correct
78	Correct	534 ms	20876 KB	Output is correct
79	Correct	466 ms	20860 KB	Output is correct
80	Correct	488 ms	20888 KB	Output is correct
81	Correct	510 ms	20876 KB	Output is correct
82	Correct	494 ms	21000 KB	Output is correct
83	Correct	488 ms	20824 KB	Output is correct
84	Correct	500 ms	20792 KB	Output is correct
85	Correct	518 ms	20792 KB	Output is correct
86	Correct	502 ms	20912 KB	Output is correct
87	Correct	512 ms	20908 KB	Output is correct
88	Correct	520 ms	20668 KB	Output is correct
89	Correct	529 ms	20684 KB	Output is correct
90	Correct	519 ms	20676 KB	Output is correct
91	Correct	514 ms	20556 KB	Output is correct
92	Correct	520 ms	20556 KB	Output is correct