oj.uz

Submission #535722

# Submission time Handle Problem Language Result Execution time Memory
535722 2022-03-11T03:07:49 Z louiskwok Mecho (IOI09_mecho) C++17
51 / 100
 1000 ms 6904 KB 
#include <bits/stdc++.h>
using namespace std;
bool visited[805][805];
int distBee[805][805];
int distBear[805][805];
char g[805][805];
int dr[] = {-1,0,1,0};
int dc[] = {0,1,0,-1};
int n,s,sr,sc,er,ec,mxtime;
bool success;
bool possible(int t) {
    memset(visited,0,sizeof visited);
    queue < pair <pair<int,int>,int> > bfs;
    bfs.push({{sr,sc},0});
    visited[sr][sc] = true;
    distBear[sr][sc] = t;
    while (!bfs.empty()) {
        int curR = bfs.front().first.first;
        int curC = bfs.front().first.second;
        int steps = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]=='T'||distBear[curR][curC]+((steps+1)%s==0?1:0)>=distBee[nr][nc]) continue;
            visited[nr][nc] = true;
            distBear[nr][nc] = distBear[curR][curC] + ((steps+1)%s==0?1:0);
            bfs.push({{nr,nc},steps+1});
        }
    }
    if (visited[er][ec]) {
        success = true;
        return true;
    }
    return false;
}
int main() {
    queue < pair<int,int> > bfs;
    cin >> n >> s;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            cin >> g[i][j];
            distBee[i][j]=1000000;
            if (g[i][j]=='M') sr = i,sc = j;
            else if (g[i][j]=='D') er = i,ec = j;
            else if (g[i][j]=='H') {
                visited[i][j] = true;
                distBee[i][j] = 0;
                bfs.push({i,j});
            }
        }
    }
    while (!bfs.empty()) {
        int curR = bfs.front().first;
        int curC = bfs.front().second;
        bfs.pop();
        for (int i=0;i<4;i++) {
            int nr = curR + dr[i];
            int nc = curC + dc[i];
            if (nr<1||nr>n||nc<1||nc>n||visited[nr][nc]||g[nr][nc]!='G') continue;
            visited[nr][nc] = true;
            distBee[nr][nc] = distBee[curR][curC]+1;
            mxtime = max(mxtime,distBee[nr][nc]);
            bfs.push({nr,nc});
        }
    }
    int lo = 0,hi = mxtime;
    for (int i=mxtime;i>=0;i--) {
        if (possible(i)) return cout << i << endl,0;
    }
    cout << -1 << endl;
    return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:67:9: warning: unused variable 'lo' [-Wunused-variable]
   67 |     int lo = 0,hi = mxtime;
      |         ^~
mecho.cpp:67:16: warning: unused variable 'hi' [-Wunused-variable]
   67 |     int lo = 0,hi = mxtime;
      |                ^~

Subtask #1
51.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Execution timed out 1094 ms 5348 KB Time limit exceeded
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct
13 Incorrect 2 ms 1192 KB Output isn't correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 980 KB Output is correct
16 Correct 2 ms 980 KB Output is correct
17 Correct 2 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 2 ms 980 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
21 Correct 2 ms 1108 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 2 ms 1108 KB Output is correct
24 Correct 2 ms 1108 KB Output is correct
25 Correct 3 ms 1108 KB Output is correct
26 Correct 3 ms 1108 KB Output is correct
27 Correct 4 ms 1132 KB Output is correct
28 Correct 2 ms 1108 KB Output is correct
29 Correct 4 ms 1236 KB Output is correct
30 Correct 2 ms 1236 KB Output is correct
31 Correct 5 ms 1248 KB Output is correct
32 Correct 3 ms 1236 KB Output is correct
33 Correct 28 ms 2260 KB Output is correct
34 Correct 15 ms 2336 KB Output is correct
35 Correct 290 ms 3404 KB Output is correct
36 Correct 30 ms 2516 KB Output is correct
37 Correct 21 ms 2528 KB Output is correct
38 Correct 468 ms 3808 KB Output is correct
39 Correct 40 ms 2716 KB Output is correct
40 Correct 28 ms 2716 KB Output is correct
41 Correct 730 ms 4128 KB Output is correct
42 Correct 38 ms 2900 KB Output is correct
43 Correct 27 ms 2900 KB Output is correct
44 Correct 916 ms 4472 KB Output is correct
45 Correct 48 ms 3028 KB Output is correct
46 Correct 34 ms 3000 KB Output is correct
47 Execution timed out 1087 ms 4828 KB Time limit exceeded
48 Correct 65 ms 3300 KB Output is correct
49 Correct 44 ms 3292 KB Output is correct
50 Execution timed out 1096 ms 5180 KB Time limit exceeded
51 Correct 65 ms 3488 KB Output is correct
52 Correct 54 ms 3492 KB Output is correct
53 Execution timed out 1096 ms 5540 KB Time limit exceeded
54 Correct 64 ms 3696 KB Output is correct
55 Correct 49 ms 3692 KB Output is correct
56 Execution timed out 1097 ms 5864 KB Time limit exceeded
57 Correct 80 ms 3896 KB Output is correct
58 Correct 58 ms 3900 KB Output is correct
59 Execution timed out 1097 ms 6156 KB Time limit exceeded
60 Correct 79 ms 4088 KB Output is correct
61 Correct 71 ms 4012 KB Output is correct
62 Execution timed out 1098 ms 6524 KB Time limit exceeded
63 Execution timed out 1099 ms 5360 KB Time limit exceeded
64 Execution timed out 1099 ms 5664 KB Time limit exceeded
65 Execution timed out 1096 ms 5652 KB Time limit exceeded
66 Execution timed out 1077 ms 5568 KB Time limit exceeded
67 Execution timed out 1101 ms 5512 KB Time limit exceeded
68 Correct 163 ms 6544 KB Output is correct
69 Correct 83 ms 6604 KB Output is correct
70 Correct 87 ms 6660 KB Output is correct
71 Correct 88 ms 6548 KB Output is correct
72 Incorrect 54 ms 4484 KB Output isn't correct
73 Incorrect 644 ms 6864 KB Output isn't correct
74 Correct 349 ms 6868 KB Output is correct
75 Correct 648 ms 6864 KB Output is correct
76 Correct 548 ms 6904 KB Output is correct
77 Correct 585 ms 6864 KB Output is correct
78 Execution timed out 1081 ms 5496 KB Time limit exceeded
79 Correct 167 ms 5096 KB Output is correct
80 Correct 385 ms 5252 KB Output is correct
81 Correct 799 ms 5324 KB Output is correct
82 Correct 421 ms 5292 KB Output is correct
83 Execution timed out 1090 ms 5516 KB Time limit exceeded
84 Correct 588 ms 5252 KB Output is correct
85 Correct 307 ms 5432 KB Output is correct
86 Correct 796 ms 5596 KB Output is correct
87 Correct 739 ms 5284 KB Output is correct
88 Execution timed out 1073 ms 5796 KB Time limit exceeded
89 Correct 727 ms 5448 KB Output is correct
90 Execution timed out 1079 ms 5392 KB Time limit exceeded
91 Correct 917 ms 5452 KB Output is correct
92 Execution timed out 1089 ms 5488 KB Time limit exceeded