oj.uz

Submission #583978

# Submission time Handle Problem Language Result Execution time Memory
583978 2022-06-26T15:23:21 Z Omar_Elgedawy Mecho (IOI09_mecho) C++14
10 / 100
 381 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],vis[N][N],n,s;
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){
  queue<cell>cu;
  cu.push({i,j,st});
  memset(vis,0,sizeof vis);
  vis[i][j]=1;
  int t;
  while(cu.size()){
    i=cu.front().i;
    j=cu.front().j;
    t=cu.front().t;
    cu.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]){
        cu.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;
    }
  }
  memset(vis,0,sizeof vis);
  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;
    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:102:15: warning: 'yst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |     int x=bfs2(xst,yst,m);
      |           ~~~~^~~~~~~~~~~
mecho.cpp:102: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 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Incorrect 2 ms 2772 KB Output isn't correct
4 Incorrect 2 ms 2772 KB Output isn't correct
5 Incorrect 2 ms 2772 KB Output isn't correct
6 Correct 2 ms 2772 KB Output is correct
7 Runtime error 187 ms 65536 KB Execution killed with signal 9
8 Incorrect 2 ms 2900 KB Output isn't correct
9 Correct 2 ms 2900 KB Output is correct
10 Incorrect 2 ms 2900 KB Output isn't correct
11 Correct 2 ms 2908 KB Output is correct
12 Incorrect 2 ms 3028 KB Output isn't correct
13 Incorrect 21 ms 3668 KB Output isn't correct
14 Correct 244 ms 17780 KB Output is correct
15 Incorrect 2 ms 2900 KB Output isn't correct
16 Incorrect 2 ms 2900 KB Output isn't correct
17 Incorrect 2 ms 2900 KB Output isn't correct
18 Incorrect 2 ms 2900 KB Output isn't correct
19 Incorrect 2 ms 2900 KB Output isn't correct
20 Incorrect 2 ms 2900 KB Output isn't correct
21 Incorrect 2 ms 2900 KB Output isn't correct
22 Incorrect 2 ms 2900 KB Output isn't correct
23 Incorrect 2 ms 3028 KB Output isn't correct
24 Incorrect 2 ms 3028 KB Output isn't correct
25 Incorrect 2 ms 3028 KB Output isn't correct
26 Incorrect 3 ms 3072 KB Output isn't correct
27 Incorrect 3 ms 3028 KB Output isn't correct
28 Incorrect 3 ms 3028 KB Output isn't correct
29 Incorrect 2 ms 3028 KB Output isn't correct
30 Incorrect 2 ms 3028 KB Output isn't correct
31 Incorrect 4 ms 3072 KB Output isn't correct
32 Incorrect 3 ms 3028 KB Output isn't correct
33 Incorrect 6 ms 4220 KB Output isn't correct
34 Incorrect 7 ms 4212 KB Output isn't correct
35 Runtime error 169 ms 65536 KB Execution killed with signal 9
36 Incorrect 10 ms 4308 KB Output isn't correct
37 Incorrect 9 ms 4308 KB Output isn't correct
38 Runtime error 169 ms 65536 KB Execution killed with signal 9
39 Incorrect 10 ms 4564 KB Output isn't correct
40 Incorrect 10 ms 4564 KB Output isn't correct
41 Runtime error 175 ms 65536 KB Execution killed with signal 9
42 Incorrect 14 ms 4820 KB Output isn't correct
43 Incorrect 12 ms 4692 KB Output isn't correct
44 Runtime error 195 ms 65536 KB Execution killed with signal 9
45 Incorrect 13 ms 4948 KB Output isn't correct
46 Incorrect 13 ms 4948 KB Output isn't correct
47 Runtime error 166 ms 65536 KB Execution killed with signal 9
48 Incorrect 16 ms 5204 KB Output isn't correct
49 Incorrect 15 ms 5204 KB Output isn't correct
50 Runtime error 175 ms 65536 KB Execution killed with signal 9
51 Incorrect 17 ms 5404 KB Output isn't correct
52 Incorrect 17 ms 5296 KB Output isn't correct
53 Runtime error 182 ms 65536 KB Execution killed with signal 9
54 Incorrect 20 ms 5604 KB Output isn't correct
55 Incorrect 19 ms 5476 KB Output isn't correct
56 Runtime error 162 ms 65536 KB Execution killed with signal 9
57 Incorrect 22 ms 5796 KB Output isn't correct
58 Incorrect 23 ms 5684 KB Output isn't correct
59 Runtime error 166 ms 65536 KB Execution killed with signal 9
60 Incorrect 28 ms 6000 KB Output isn't correct
61 Incorrect 25 ms 5940 KB Output isn't correct
62 Runtime error 168 ms 65536 KB Execution killed with signal 9
63 Correct 116 ms 5976 KB Output is correct
64 Correct 220 ms 5984 KB Output is correct
65 Incorrect 188 ms 5920 KB Output isn't correct
66 Incorrect 144 ms 5916 KB Output isn't correct
67 Correct 118 ms 5972 KB Output is correct
68 Incorrect 57 ms 6020 KB Output isn't correct
69 Correct 59 ms 5960 KB Output is correct
70 Correct 46 ms 6004 KB Output is correct
71 Correct 52 ms 5972 KB Output is correct
72 Incorrect 48 ms 5984 KB Output isn't correct
73 Runtime error 381 ms 65536 KB Execution killed with signal 9
74 Runtime error 325 ms 65536 KB Execution killed with signal 9
75 Runtime error 299 ms 65536 KB Execution killed with signal 9
76 Runtime error 291 ms 65536 KB Execution killed with signal 9
77 Runtime error 300 ms 65536 KB Execution killed with signal 9
78 Runtime error 255 ms 65536 KB Execution killed with signal 9
79 Runtime error 251 ms 65536 KB Execution killed with signal 9
80 Runtime error 249 ms 65536 KB Execution killed with signal 9
81 Runtime error 264 ms 65536 KB Execution killed with signal 9
82 Runtime error 247 ms 65536 KB Execution killed with signal 9
83 Runtime error 225 ms 65536 KB Execution killed with signal 9
84 Runtime error 234 ms 65536 KB Execution killed with signal 9
85 Runtime error 219 ms 65536 KB Execution killed with signal 9
86 Runtime error 226 ms 65536 KB Execution killed with signal 9
87 Runtime error 219 ms 65536 KB Execution killed with signal 9
88 Runtime error 204 ms 65536 KB Execution killed with signal 9
89 Runtime error 207 ms 65536 KB Execution killed with signal 9
90 Runtime error 203 ms 65536 KB Execution killed with signal 9
91 Runtime error 198 ms 65536 KB Execution killed with signal 9
92 Runtime error 206 ms 65536 KB Execution killed with signal 9