Submission #583171

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
583171	2022-06-25T00:16:04 Z	HeyYouNotYouYou	Mecho (IOI09_mecho)	C++14	42 / 100	630 ms	21164 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},0});
  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

42.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	Incorrect	0 ms	212 KB	Output isn't correct
6	Incorrect	0 ms	340 KB	Output isn't correct
7	Incorrect	475 ms	20696 KB	Output isn't correct
8	Incorrect	0 ms	340 KB	Output isn't correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Incorrect	2 ms	596 KB	Output isn't correct
13	Correct	2 ms	596 KB	Output is correct
14	Correct	2 ms	596 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Incorrect	1 ms	340 KB	Output isn't correct
17	Correct	1 ms	340 KB	Output is correct
18	Incorrect	1 ms	340 KB	Output isn't correct
19	Correct	1 ms	340 KB	Output is correct
20	Incorrect	1 ms	360 KB	Output isn't correct
21	Correct	1 ms	468 KB	Output is correct
22	Incorrect	1 ms	468 KB	Output isn't correct
23	Correct	1 ms	468 KB	Output is correct
24	Incorrect	1 ms	468 KB	Output isn't correct
25	Correct	1 ms	596 KB	Output is correct
26	Incorrect	1 ms	596 KB	Output isn't correct
27	Correct	2 ms	596 KB	Output is correct
28	Incorrect	2 ms	596 KB	Output isn't correct
29	Correct	2 ms	724 KB	Output is correct
30	Incorrect	2 ms	724 KB	Output isn't correct
31	Correct	2 ms	772 KB	Output is correct
32	Incorrect	2 ms	724 KB	Output isn't correct
33	Correct	35 ms	5304 KB	Output is correct
34	Incorrect	49 ms	5360 KB	Output isn't correct
35	Correct	71 ms	5368 KB	Output is correct
36	Correct	46 ms	6604 KB	Output is correct
37	Incorrect	49 ms	6564 KB	Output isn't correct
38	Correct	81 ms	6568 KB	Output is correct
39	Correct	58 ms	7848 KB	Output is correct
40	Incorrect	64 ms	7764 KB	Output isn't correct
41	Correct	121 ms	7872 KB	Output is correct
42	Correct	85 ms	9292 KB	Output is correct
43	Incorrect	84 ms	9288 KB	Output isn't correct
44	Correct	157 ms	9424 KB	Output is correct
45	Correct	123 ms	10796 KB	Output is correct
46	Incorrect	104 ms	10832 KB	Output isn't correct
47	Correct	191 ms	10972 KB	Output is correct
48	Correct	128 ms	12444 KB	Output is correct
49	Incorrect	121 ms	12496 KB	Output isn't correct
50	Correct	220 ms	12616 KB	Output is correct
51	Correct	143 ms	14272 KB	Output is correct
52	Incorrect	146 ms	14272 KB	Output isn't correct
53	Correct	293 ms	14296 KB	Output is correct
54	Correct	168 ms	16172 KB	Output is correct
55	Incorrect	171 ms	16076 KB	Output isn't correct
56	Correct	377 ms	16196 KB	Output is correct
57	Correct	189 ms	18124 KB	Output is correct
58	Incorrect	193 ms	18132 KB	Output isn't correct
59	Correct	429 ms	18336 KB	Output is correct
60	Correct	227 ms	20428 KB	Output is correct
61	Incorrect	226 ms	20352 KB	Output isn't correct
62	Correct	517 ms	20336 KB	Output is correct
63	Correct	522 ms	20352 KB	Output is correct
64	Correct	630 ms	20352 KB	Output is correct
65	Correct	573 ms	20480 KB	Output is correct
66	Incorrect	582 ms	20556 KB	Output isn't correct
67	Correct	524 ms	20348 KB	Output is correct
68	Correct	535 ms	20392 KB	Output is correct
69	Correct	567 ms	20404 KB	Output is correct
70	Correct	549 ms	20396 KB	Output is correct
71	Correct	571 ms	20400 KB	Output is correct
72	Correct	512 ms	20428 KB	Output is correct
73	Correct	532 ms	20952 KB	Output is correct
74	Correct	571 ms	21152 KB	Output is correct
75	Correct	595 ms	21164 KB	Output is correct
76	Correct	545 ms	21044 KB	Output is correct
77	Correct	592 ms	20952 KB	Output is correct
78	Correct	513 ms	20880 KB	Output is correct
79	Correct	475 ms	20992 KB	Output is correct
80	Correct	475 ms	20868 KB	Output is correct
81	Correct	504 ms	20832 KB	Output is correct
82	Correct	484 ms	20940 KB	Output is correct
83	Correct	503 ms	20792 KB	Output is correct
84	Correct	488 ms	20860 KB	Output is correct
85	Correct	530 ms	20820 KB	Output is correct
86	Correct	483 ms	20796 KB	Output is correct
87	Correct	491 ms	20916 KB	Output is correct
88	Correct	483 ms	20676 KB	Output is correct
89	Correct	502 ms	20676 KB	Output is correct
90	Correct	506 ms	20836 KB	Output is correct
91	Correct	502 ms	20676 KB	Output is correct
92	Correct	520 ms	20676 KB	Output is correct