oj.uz

답안 #583969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583969 2022-06-26T15:12:28 Z Omar_Elgedawy Mecho (IOI09_mecho) C++14
6 / 100
 283 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,dp[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});
      }
    }
  }
}
void bfs2(int i,int j){
  int t=0;
  q.push({i,j,t});
  dp[i][j]=0;
  while(q.size()){
    i=q.front().i;
    j=q.front().j;
    t=q.front().t;
    q.pop();
    if(grid[i][j]=='D')continue;
    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')&&
         dp[x][y]>t+1&&block[x][y]>(t+1)/s){
        q.push({x,y,t+1});
        dp[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;
      dp[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;
  // }
  bfs2(xst,yst);
  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:93:15: warning: variable 'xed' set but not used [-Wunused-but-set-variable]
   93 |   int xst,yst,xed,yed;
      |               ^~~
mecho.cpp:93:19: warning: variable 'yed' set but not used [-Wunused-but-set-variable]
   93 |   int xst,yst,xed,yed;
      |                   ^~~
mecho.cpp:125:15: warning: 'yst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  125 |     int x=bfs3(xst,yst,m);
      |           ~~~~^~~~~~~~~~~
mecho.cpp:125:15: warning: 'xst' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
6.0 / 100.0

# 결과 실행 시간 메모리 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 2 ms 2868 KB Output isn't correct
6 Correct 2 ms 2900 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 2868 KB Output is correct
10 Incorrect 2 ms 2900 KB Output isn't correct
11 Correct 2 ms 2900 KB Output is correct
12 Incorrect 2 ms 3156 KB Output isn't correct
13 Incorrect 15 ms 3760 KB Output isn't correct
14 Incorrect 220 ms 17980 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 3000 KB Output isn't correct
18 Incorrect 2 ms 2900 KB Output isn't correct
19 Incorrect 2 ms 3028 KB Output isn't correct
20 Incorrect 2 ms 3028 KB Output isn't correct
21 Incorrect 3 ms 3028 KB Output isn't correct
22 Incorrect 2 ms 3028 KB Output isn't correct
23 Incorrect 2 ms 3156 KB Output isn't correct
24 Incorrect 2 ms 3156 KB Output isn't correct
25 Incorrect 3 ms 3156 KB Output isn't correct
26 Incorrect 2 ms 3284 KB Output isn't correct
27 Incorrect 2 ms 3256 KB Output isn't correct
28 Incorrect 3 ms 3284 KB Output isn't correct
29 Incorrect 3 ms 3284 KB Output isn't correct
30 Incorrect 3 ms 3284 KB Output isn't correct
31 Incorrect 2 ms 3284 KB Output isn't correct
32 Incorrect 3 ms 3384 KB Output isn't correct
33 Incorrect 9 ms 5452 KB Output isn't correct
34 Incorrect 13 ms 5452 KB Output isn't correct
35 Runtime error 161 ms 65536 KB Execution killed with signal 9
36 Incorrect 12 ms 5848 KB Output isn't correct
37 Incorrect 11 ms 5844 KB Output isn't correct
38 Runtime error 161 ms 65536 KB Execution killed with signal 9
39 Incorrect 12 ms 6240 KB Output isn't correct
40 Incorrect 17 ms 6240 KB Output isn't correct
41 Runtime error 154 ms 65536 KB Execution killed with signal 9
42 Incorrect 17 ms 6600 KB Output isn't correct
43 Incorrect 14 ms 6640 KB Output isn't correct
44 Runtime error 168 ms 65536 KB Execution killed with signal 9
45 Incorrect 16 ms 6916 KB Output isn't correct
46 Incorrect 18 ms 7040 KB Output isn't correct
47 Runtime error 159 ms 65536 KB Execution killed with signal 9
48 Incorrect 19 ms 7380 KB Output isn't correct
49 Incorrect 20 ms 7436 KB Output isn't correct
50 Runtime error 169 ms 65536 KB Execution killed with signal 9
51 Incorrect 21 ms 7764 KB Output isn't correct
52 Incorrect 23 ms 7760 KB Output isn't correct
53 Runtime error 169 ms 65536 KB Execution killed with signal 9
54 Incorrect 23 ms 8268 KB Output isn't correct
55 Incorrect 25 ms 8340 KB Output isn't correct
56 Runtime error 165 ms 65536 KB Execution killed with signal 9
57 Incorrect 26 ms 8664 KB Output isn't correct
58 Incorrect 30 ms 8696 KB Output isn't correct
59 Runtime error 163 ms 65536 KB Execution killed with signal 9
60 Incorrect 29 ms 9128 KB Output isn't correct
61 Incorrect 32 ms 9096 KB Output isn't correct
62 Runtime error 166 ms 65536 KB Execution killed with signal 9
63 Correct 127 ms 9128 KB Output is correct
64 Correct 229 ms 9128 KB Output is correct
65 Incorrect 198 ms 9132 KB Output isn't correct
66 Incorrect 142 ms 9132 KB Output isn't correct
67 Incorrect 134 ms 9128 KB Output isn't correct
68 Incorrect 64 ms 9112 KB Output isn't correct
69 Correct 64 ms 9160 KB Output is correct
70 Correct 54 ms 9172 KB Output is correct
71 Correct 55 ms 9172 KB Output is correct
72 Incorrect 50 ms 9172 KB Output isn't correct
73 Runtime error 282 ms 65536 KB Execution killed with signal 9
74 Runtime error 272 ms 65536 KB Execution killed with signal 9
75 Runtime error 283 ms 65536 KB Execution killed with signal 9
76 Runtime error 277 ms 65536 KB Execution killed with signal 9
77 Runtime error 278 ms 65536 KB Execution killed with signal 9
78 Runtime error 239 ms 65536 KB Execution killed with signal 9
79 Runtime error 255 ms 65536 KB Execution killed with signal 9
80 Runtime error 241 ms 65536 KB Execution killed with signal 9
81 Runtime error 240 ms 65536 KB Execution killed with signal 9
82 Runtime error 235 ms 65536 KB Execution killed with signal 9
83 Runtime error 216 ms 65536 KB Execution killed with signal 9
84 Runtime error 216 ms 65536 KB Execution killed with signal 9
85 Runtime error 219 ms 65536 KB Execution killed with signal 9
86 Runtime error 218 ms 65536 KB Execution killed with signal 9
87 Runtime error 216 ms 65536 KB Execution killed with signal 9
88 Runtime error 197 ms 65536 KB Execution killed with signal 9
89 Runtime error 194 ms 65536 KB Execution killed with signal 9
90 Runtime error 193 ms 65536 KB Execution killed with signal 9
91 Runtime error 192 ms 65536 KB Execution killed with signal 9
92 Runtime error 197 ms 65536 KB Execution killed with signal 9