oj.uz

Submission #583979

# Submission time Handle Problem Language Result Execution time Memory
583979 2022-06-26T15:25:50 Z Omar_Elgedawy Mecho (IOI09_mecho) C++14
10 / 100
 301 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
// #define int             long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=8e2+5,M=1e2+5,Mod=1e9;
char grid[N][N];
int block[N][N],n,s;
bool vis[N][N];
int valid(int i,int j){
  return (i>=0&&j>=0&&i<n&&j<n);
}
struct cell{
  int i;
  int j;
  int t;
};
queue<cell>q;
void bfs(){
  while(q.size()){
    int i=q.front().i;
    int j=q.front().j;
    int t=q.front().t;
    q.pop();
    vis[i][j]=1;
    block[i][j]=min(t,block[i][j]);
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&grid[x][y]=='G'&&!vis[x][y]){
        q.push({x,y,t+1});
      }
    }
  }
}
bool bfs2(int i,int j,int st){
  while(q.size())q.pop();
  q.push({i,j,st});
  vis[i][j]=1;
  int t;
  while(q.size()){
    i=q.front().i;
    j=q.front().j;
    t=q.front().t;
    q.pop();
    if(grid[i][j]=='D')return 1;
    for(int k=0;k<4;k++){
      int x=dx[k]+i;
      int y=dy[k]+j;
      if(valid(x,y)&&(grid[x][y]=='G'||grid[x][y]=='D')&&block[x][y]>=st+(t+1)/s&&!vis[x][y]){
        q.push({x,y,t+1});
        vis[x][y]=1;
      }
    }
  }
  return 0;
}
void testcase(int h){
  cin>>n>>s;
  int xst,yst,xed,yed;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      block[i][j]=1e9;
    }
  }
  for(int i=0;i<n;i++){
    string s;cin>>s;
    for(int j=0;j<n;j++){
      grid[i][j]=s[j];
      if(s[j]=='T')
        block[i][j]=-1;
      if(s[j]=='H')
        q.push({i,j,0});
      if(s[j]=='M')xst=i,yst=j;
      if(s[j]=='D')xed=i,yed=j;
    }
  }
  bfs();
  // for(int i=0;i<n;i++){
  //   for(int j=0;j<n;j++){
  //     cout<<block[i][j]<<' ';
  //   }cout<<el;
  // }
  int l=0,r=n*n+1;
  int mx=-1;
  while(l<=r){
    int m=(l+r)/2;
    // cout<<l<<' '<<m<<' '<<r<<el;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        vis[i][j]=0;
    int x=bfs2(xst,yst,m);
    if(x){
      mx=m;
      l=m+1;
    }
    else{
      r=m-1;
    }
  }
  cout<<mx<<el;
}
int32_t main()
{
  // fast
  testcase(1);
  // int tc;cin>>tc;for(int i=1;i<=tc;i++)testcase(i);
  return 0;
}

Compilation message

mecho.cpp: In function 'void testcase(int)':
mecho.cpp:72:15: warning: variable 'xed' set but not used [-Wunused-but-set-variable]
   72 |   int xst,yst,xed,yed;
      |               ^~~
mecho.cpp:72:19: warning: variable 'yed' set but not used [-Wunused-but-set-variable]
   72 |   int xst,yst,xed,yed;
      |                   ^~~
mecho.cpp:104:15: warning: 'yst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |     int x=bfs2(xst,yst,m);
      |           ~~~~^~~~~~~~~~~
mecho.cpp:104:15: warning: 'xst' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Incorrect 0 ms 340 KB Output isn't correct
6 Correct 0 ms 340 KB Output is correct
7 Runtime error 190 ms 65536 KB Execution killed with signal 9
8 Incorrect 1 ms 340 KB Output isn't correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Correct 1 ms 340 KB Output is correct
12 Incorrect 1 ms 596 KB Output isn't correct
13 Incorrect 15 ms 1108 KB Output isn't correct
14 Correct 231 ms 15208 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 0 ms 340 KB Output isn't correct
20 Incorrect 0 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 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 1 ms 596 KB Output isn't correct
28 Incorrect 1 ms 596 KB Output isn't correct
29 Incorrect 1 ms 596 KB Output isn't correct
30 Incorrect 1 ms 596 KB Output isn't correct
31 Incorrect 1 ms 596 KB Output isn't correct
32 Incorrect 1 ms 596 KB Output isn't correct
33 Incorrect 6 ms 1876 KB Output isn't correct
34 Incorrect 6 ms 1876 KB Output isn't correct
35 Runtime error 175 ms 65536 KB Execution killed with signal 9
36 Incorrect 6 ms 2132 KB Output isn't correct
37 Incorrect 7 ms 2172 KB Output isn't correct
38 Runtime error 173 ms 65536 KB Execution killed with signal 9
39 Incorrect 9 ms 2388 KB Output isn't correct
40 Incorrect 8 ms 2388 KB Output isn't correct
41 Runtime error 162 ms 65536 KB Execution killed with signal 9
42 Incorrect 9 ms 2668 KB Output isn't correct
43 Incorrect 9 ms 2608 KB Output isn't correct
44 Runtime error 161 ms 65536 KB Execution killed with signal 9
45 Incorrect 12 ms 2900 KB Output isn't correct
46 Incorrect 12 ms 2868 KB Output isn't correct
47 Runtime error 172 ms 65536 KB Execution killed with signal 9
48 Incorrect 16 ms 3084 KB Output isn't correct
49 Incorrect 13 ms 3156 KB Output isn't correct
50 Runtime error 163 ms 65536 KB Execution killed with signal 9
51 Incorrect 15 ms 3332 KB Output isn't correct
52 Incorrect 15 ms 3280 KB Output isn't correct
53 Runtime error 171 ms 65536 KB Execution killed with signal 9
54 Incorrect 22 ms 3488 KB Output isn't correct
55 Incorrect 19 ms 3504 KB Output isn't correct
56 Runtime error 187 ms 65536 KB Execution killed with signal 9
57 Incorrect 22 ms 3812 KB Output isn't correct
58 Incorrect 21 ms 3796 KB Output isn't correct
59 Runtime error 171 ms 65536 KB Execution killed with signal 9
60 Incorrect 23 ms 4044 KB Output isn't correct
61 Incorrect 23 ms 4016 KB Output isn't correct
62 Runtime error 190 ms 65536 KB Execution killed with signal 9
63 Correct 106 ms 4076 KB Output is correct
64 Correct 192 ms 4080 KB Output is correct
65 Incorrect 166 ms 4080 KB Output isn't correct
66 Incorrect 138 ms 4076 KB Output isn't correct
67 Correct 114 ms 3992 KB Output is correct
68 Incorrect 56 ms 4128 KB Output isn't correct
69 Correct 54 ms 4120 KB Output is correct
70 Correct 44 ms 4120 KB Output is correct
71 Correct 48 ms 4116 KB Output is correct
72 Incorrect 44 ms 4124 KB Output isn't correct
73 Runtime error 301 ms 65536 KB Execution killed with signal 9
74 Runtime error 290 ms 65536 KB Execution killed with signal 9
75 Runtime error 283 ms 65536 KB Execution killed with signal 9
76 Runtime error 301 ms 65536 KB Execution killed with signal 9
77 Runtime error 295 ms 65536 KB Execution killed with signal 9
78 Runtime error 276 ms 65536 KB Execution killed with signal 9
79 Runtime error 282 ms 65536 KB Execution killed with signal 9
80 Runtime error 257 ms 65536 KB Execution killed with signal 9
81 Runtime error 272 ms 65536 KB Execution killed with signal 9
82 Runtime error 254 ms 65536 KB Execution killed with signal 9
83 Runtime error 223 ms 65536 KB Execution killed with signal 9
84 Runtime error 227 ms 65536 KB Execution killed with signal 9
85 Runtime error 248 ms 65536 KB Execution killed with signal 9
86 Runtime error 230 ms 65536 KB Execution killed with signal 9
87 Runtime error 229 ms 65536 KB Execution killed with signal 9
88 Runtime error 215 ms 65536 KB Execution killed with signal 9
89 Runtime error 205 ms 65536 KB Execution killed with signal 9
90 Runtime error 202 ms 65536 KB Execution killed with signal 9
91 Runtime error 203 ms 65536 KB Execution killed with signal 9
92 Runtime error 209 ms 65536 KB Execution killed with signal 9