# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
960481 | 2024-04-10T14:07:40 Z | LmaoLmao | Mecho (IOI09_mecho) | C++17 | 3 ms | 600 KB |
#include<bits/stdc++.h> using namespace std; #define fi first #define se second using ll = long long; using ii = pair<int, int>; const int N = 1e6+5; const int INF = 1e9; int d[1000][1000],m[1000][1000],n,s; char a[1000][1000]; int dx[4]={1,0,0,-1}; int dy[4]={0,1,-1,0}; ii pos,h; bool bfs(int x) { queue<ii> q; q.push(pos); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { m[i][j]=0; } } while(!q.empty()) { ii u=q.front(); q.pop(); for(int i=0;i<4;i++) { ii v={u.fi+dx[i],u.se+dy[i]}; if(v.fi<0 || v.fi>=n || v.se<0 || v.se>=n) continue; if(m[v.fi][v.se]==0 && a[v.fi][v.se]!='T' && d[v.fi][v.se]-x>=(m[u.fi][u.se]+1)/s && a[v.fi][v.se]!='M') { m[v.fi][v.se]=m[u.fi][u.se]+1; q.push(v); } } } if(m[h.fi][h.se]>0) return 1; else return 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif queue<ii> q; cin >> n >> s; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin >> a[i][j]; if(a[i][j]=='H') { q.push({i,j}); } if(a[i][j]=='M') pos={i,j}; if(a[i][j]=='D') h={i,j}; } } while(!q.empty()) { ii u=q.front(); q.pop(); for(int i=0;i<4;i++) { ii v={u.fi+dx[i],u.se+dy[i]}; if(v.fi<0 || v.fi>=n || v.se<0 || v.se>=n) continue; if(d[v.fi][v.se]==0 && a[v.fi][v.se]!='T' && a[v.fi][v.se]!='H') { d[v.fi][v.se]=d[u.fi][u.se]+1; q.push(v); } } } int l=0,r=100,ans=-1; while(l<=r) { int m=(l+r)/2; if(bfs(m)) { ans=m; l=m+1; } else { r=m-1; } } cout << -1; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 348 KB | Output isn't correct |
2 | Incorrect | 3 ms | 348 KB | Output isn't correct |
3 | Incorrect | 2 ms | 348 KB | Output isn't correct |
4 | Incorrect | 2 ms | 348 KB | Output isn't correct |
5 | Incorrect | 2 ms | 348 KB | Output isn't correct |
6 | Incorrect | 2 ms | 348 KB | Output isn't correct |
7 | Incorrect | 2 ms | 348 KB | Output isn't correct |
8 | Incorrect | 2 ms | 528 KB | Output isn't correct |
9 | Incorrect | 2 ms | 348 KB | Output isn't correct |
10 | Incorrect | 2 ms | 348 KB | Output isn't correct |
11 | Incorrect | 2 ms | 344 KB | Output isn't correct |
12 | Incorrect | 2 ms | 348 KB | Output isn't correct |
13 | Incorrect | 2 ms | 348 KB | Output isn't correct |
14 | Incorrect | 2 ms | 344 KB | Output isn't correct |
15 | Incorrect | 1 ms | 348 KB | Output isn't correct |
16 | Incorrect | 1 ms | 348 KB | Output isn't correct |
17 | Incorrect | 1 ms | 348 KB | Output isn't correct |
18 | Incorrect | 1 ms | 348 KB | Output isn't correct |
19 | Incorrect | 2 ms | 348 KB | Output isn't correct |
20 | Incorrect | 2 ms | 348 KB | Output isn't correct |
21 | Incorrect | 1 ms | 348 KB | Output isn't correct |
22 | Incorrect | 2 ms | 344 KB | Output isn't correct |
23 | Incorrect | 1 ms | 344 KB | Output isn't correct |
24 | Incorrect | 1 ms | 348 KB | Output isn't correct |
25 | Incorrect | 2 ms | 532 KB | Output isn't correct |
26 | Incorrect | 1 ms | 348 KB | Output isn't correct |
27 | Incorrect | 2 ms | 348 KB | Output isn't correct |
28 | Incorrect | 2 ms | 348 KB | Output isn't correct |
29 | Incorrect | 2 ms | 348 KB | Output isn't correct |
30 | Incorrect | 2 ms | 348 KB | Output isn't correct |
31 | Incorrect | 1 ms | 348 KB | Output isn't correct |
32 | Incorrect | 2 ms | 348 KB | Output isn't correct |
33 | Incorrect | 2 ms | 348 KB | Output isn't correct |
34 | Incorrect | 2 ms | 348 KB | Output isn't correct |
35 | Incorrect | 1 ms | 348 KB | Output isn't correct |
36 | Incorrect | 2 ms | 348 KB | Output isn't correct |
37 | Incorrect | 2 ms | 348 KB | Output isn't correct |
38 | Incorrect | 2 ms | 600 KB | Output isn't correct |
39 | Incorrect | 2 ms | 348 KB | Output isn't correct |
40 | Incorrect | 1 ms | 348 KB | Output isn't correct |
41 | Incorrect | 2 ms | 348 KB | Output isn't correct |
42 | Incorrect | 2 ms | 376 KB | Output isn't correct |
43 | Incorrect | 2 ms | 348 KB | Output isn't correct |
44 | Incorrect | 1 ms | 348 KB | Output isn't correct |
45 | Incorrect | 1 ms | 348 KB | Output isn't correct |
46 | Incorrect | 2 ms | 348 KB | Output isn't correct |
47 | Incorrect | 2 ms | 348 KB | Output isn't correct |
48 | Incorrect | 2 ms | 348 KB | Output isn't correct |
49 | Incorrect | 1 ms | 348 KB | Output isn't correct |
50 | Incorrect | 2 ms | 348 KB | Output isn't correct |
51 | Incorrect | 1 ms | 348 KB | Output isn't correct |
52 | Incorrect | 2 ms | 348 KB | Output isn't correct |
53 | Incorrect | 2 ms | 348 KB | Output isn't correct |
54 | Incorrect | 1 ms | 348 KB | Output isn't correct |
55 | Incorrect | 2 ms | 348 KB | Output isn't correct |
56 | Incorrect | 3 ms | 348 KB | Output isn't correct |
57 | Incorrect | 2 ms | 348 KB | Output isn't correct |
58 | Incorrect | 1 ms | 348 KB | Output isn't correct |
59 | Incorrect | 1 ms | 344 KB | Output isn't correct |
60 | Incorrect | 2 ms | 348 KB | Output isn't correct |
61 | Incorrect | 3 ms | 348 KB | Output isn't correct |
62 | Incorrect | 2 ms | 528 KB | Output isn't correct |
63 | Incorrect | 2 ms | 344 KB | Output isn't correct |
64 | Incorrect | 2 ms | 532 KB | Output isn't correct |
65 | Incorrect | 2 ms | 348 KB | Output isn't correct |
66 | Incorrect | 1 ms | 348 KB | Output isn't correct |
67 | Incorrect | 2 ms | 348 KB | Output isn't correct |
68 | Incorrect | 2 ms | 348 KB | Output isn't correct |
69 | Incorrect | 1 ms | 348 KB | Output isn't correct |
70 | Incorrect | 2 ms | 344 KB | Output isn't correct |
71 | Incorrect | 2 ms | 348 KB | Output isn't correct |
72 | Incorrect | 2 ms | 528 KB | Output isn't correct |
73 | Incorrect | 2 ms | 348 KB | Output isn't correct |
74 | Incorrect | 1 ms | 348 KB | Output isn't correct |
75 | Incorrect | 2 ms | 348 KB | Output isn't correct |
76 | Incorrect | 1 ms | 348 KB | Output isn't correct |
77 | Incorrect | 1 ms | 348 KB | Output isn't correct |
78 | Incorrect | 2 ms | 348 KB | Output isn't correct |
79 | Incorrect | 2 ms | 348 KB | Output isn't correct |
80 | Incorrect | 1 ms | 348 KB | Output isn't correct |
81 | Incorrect | 2 ms | 348 KB | Output isn't correct |
82 | Incorrect | 2 ms | 348 KB | Output isn't correct |
83 | Incorrect | 2 ms | 536 KB | Output isn't correct |
84 | Incorrect | 2 ms | 348 KB | Output isn't correct |
85 | Incorrect | 2 ms | 348 KB | Output isn't correct |
86 | Incorrect | 2 ms | 348 KB | Output isn't correct |
87 | Incorrect | 2 ms | 348 KB | Output isn't correct |
88 | Incorrect | 2 ms | 348 KB | Output isn't correct |
89 | Incorrect | 1 ms | 348 KB | Output isn't correct |
90 | Incorrect | 1 ms | 348 KB | Output isn't correct |
91 | Incorrect | 2 ms | 344 KB | Output isn't correct |
92 | Incorrect | 2 ms | 348 KB | Output isn't correct |