oj.uz

Submission #583976

# Submission time Handle Problem Language Result Execution time Memory
583976 2022-06-26T15:21:22 Z Omar_Elgedawy Mecho (IOI09_mecho) C++14
6 / 100
 335 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 bfs3(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=0;
  while(l<=r){
    int m=(l+r)/2;
    // cout<<l<<' '<<m<<' '<<r<<el;
    int x=bfs3(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=bfs3(xst,yst,m);
      |           ~~~~^~~~~~~~~~~
mecho.cpp:102:15: warning: 'xst' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
6.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 1 ms 2772 KB Output isn't correct
6 Correct 2 ms 2772 KB Output is correct
7 Runtime error 199 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 3 ms 2900 KB Output is correct
12 Incorrect 2 ms 3028 KB Output isn't correct
13 Incorrect 15 ms 3668 KB Output isn't correct
14 Incorrect 212 ms 17780 KB Output isn't 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 3 ms 2900 KB Output isn't correct
20 Incorrect 3 ms 2900 KB Output isn't correct
21 Incorrect 4 ms 2960 KB Output isn't correct
22 Incorrect 2 ms 2900 KB Output isn't correct
23 Incorrect 3 ms 3028 KB Output isn't correct
24 Incorrect 3 ms 3028 KB Output isn't correct
25 Incorrect 2 ms 3028 KB Output isn't correct
26 Incorrect 2 ms 3028 KB Output isn't correct
27 Incorrect 3 ms 3028 KB Output isn't correct
28 Incorrect 2 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 2 ms 3064 KB Output isn't correct
32 Incorrect 3 ms 3028 KB Output isn't correct
33 Incorrect 7 ms 4180 KB Output isn't correct
34 Incorrect 7 ms 4124 KB Output isn't correct
35 Runtime error 173 ms 65536 KB Execution killed with signal 9
36 Incorrect 10 ms 4344 KB Output isn't correct
37 Incorrect 10 ms 4308 KB Output isn't correct
38 Runtime error 163 ms 65536 KB Execution killed with signal 9
39 Incorrect 9 ms 4548 KB Output isn't correct
40 Incorrect 10 ms 4612 KB Output isn't correct
41 Runtime error 163 ms 65536 KB Execution killed with signal 9
42 Incorrect 14 ms 4700 KB Output isn't correct
43 Incorrect 12 ms 4816 KB Output isn't correct
44 Runtime error 172 ms 65536 KB Execution killed with signal 9
45 Incorrect 14 ms 4948 KB Output isn't correct
46 Incorrect 14 ms 4992 KB Output isn't correct
47 Runtime error 163 ms 65536 KB Execution killed with signal 9
48 Incorrect 16 ms 5208 KB Output isn't correct
49 Incorrect 16 ms 5076 KB Output isn't correct
50 Runtime error 173 ms 65536 KB Execution killed with signal 9
51 Incorrect 18 ms 5348 KB Output isn't correct
52 Incorrect 19 ms 5332 KB Output isn't correct
53 Runtime error 164 ms 65536 KB Execution killed with signal 9
54 Incorrect 19 ms 5600 KB Output isn't correct
55 Incorrect 21 ms 5600 KB Output isn't correct
56 Runtime error 173 ms 65536 KB Execution killed with signal 9
57 Incorrect 22 ms 5796 KB Output isn't correct
58 Incorrect 21 ms 5716 KB Output isn't correct
59 Runtime error 167 ms 65536 KB Execution killed with signal 9
60 Incorrect 25 ms 5972 KB Output isn't correct
61 Incorrect 25 ms 5976 KB Output isn't correct
62 Runtime error 173 ms 65536 KB Execution killed with signal 9
63 Correct 109 ms 5976 KB Output is correct
64 Correct 244 ms 5984 KB Output is correct
65 Incorrect 190 ms 5872 KB Output isn't correct
66 Incorrect 135 ms 5980 KB Output isn't correct
67 Incorrect 125 ms 5980 KB Output isn't correct
68 Incorrect 60 ms 6036 KB Output isn't correct
69 Correct 65 ms 5972 KB Output is correct
70 Correct 49 ms 5952 KB Output is correct
71 Correct 52 ms 6024 KB Output is correct
72 Incorrect 43 ms 5936 KB Output isn't correct
73 Runtime error 300 ms 65536 KB Execution killed with signal 9
74 Runtime error 335 ms 65536 KB Execution killed with signal 9
75 Runtime error 331 ms 65536 KB Execution killed with signal 9
76 Runtime error 331 ms 65536 KB Execution killed with signal 9
77 Runtime error 297 ms 65536 KB Execution killed with signal 9
78 Runtime error 280 ms 65536 KB Execution killed with signal 9
79 Runtime error 245 ms 65536 KB Execution killed with signal 9
80 Runtime error 268 ms 65536 KB Execution killed with signal 9
81 Runtime error 263 ms 65536 KB Execution killed with signal 9
82 Runtime error 245 ms 65536 KB Execution killed with signal 9
83 Runtime error 228 ms 65536 KB Execution killed with signal 9
84 Runtime error 235 ms 65536 KB Execution killed with signal 9
85 Runtime error 225 ms 65536 KB Execution killed with signal 9
86 Runtime error 231 ms 65536 KB Execution killed with signal 9
87 Runtime error 245 ms 65536 KB Execution killed with signal 9
88 Runtime error 208 ms 65536 KB Execution killed with signal 9
89 Runtime error 200 ms 65536 KB Execution killed with signal 9
90 Runtime error 212 ms 65536 KB Execution killed with signal 9
91 Runtime error 210 ms 65536 KB Execution killed with signal 9
92 Runtime error 204 ms 65536 KB Execution killed with signal 9