oj.uz

Submission #746784

# Submission time Handle Problem Language Result Execution time Memory
746784 2023-05-23T05:55:50 Z Github Tracks in the Snow (BOI13_tracks) C++14
31.7708 / 100
 663 ms 223544 KB 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const int MAXN = 4010;

char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int dX[] = {1, -1, 0, 0};
int dY[] = {0, 0, 1, -1};
int h, w;

bool possibility(int x, int y){
    if (x >= 0 && x < h && y >= 0 && y < w && grid[x][y] != '.'){
        return true;
    }
    return false;
}

int main(){
    speedup
    cin >> h >> w;
    for (int i = 0; i < h; i++){
        string s; cin >> s;
        for (int j = 0; j < w; j++){
            grid[i][j] = s[j];
        }
    }
    deque<pair<int, int>> q;
    q.push_front({0, 0});
    memset(dist, 0, sizeof dist);
    dist[0][0] = 1;
    int ans = 1;
    while (!q.empty()){
        auto &[x, y] = q.front(); q.pop_front();
        for (int i = 0; i < 4; i++){
            int nX = x+dX[i], nY = y+dY[i];
            if (possibility(nX, nY) && dist[nX][nY] == 0){
                if (grid[nX][nY] == grid[x][y]){
                    dist[nX][nY] = dist[x][y];
                    q.push_front({nX, nY});
                }else{
                    dist[nX][nY] = dist[x][y]+1;
                    q.push_back({nX, nY});
                }
            }
        }
        ans = max(ans, dist[x][y]);
    }
    cout << ans << endl;
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:42:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto &[x, y] = q.front(); q.pop_front();
      |               ^

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 65100 KB Output isn't correct
2 Correct 23 ms 63324 KB Output is correct
3 Incorrect 23 ms 63440 KB Output isn't correct
4 Incorrect 31 ms 65240 KB Output isn't correct
5 Incorrect 25 ms 64380 KB Output isn't correct
6 Correct 23 ms 63308 KB Output is correct
7 Incorrect 24 ms 63396 KB Output isn't correct
8 Incorrect 29 ms 63576 KB Output isn't correct
9 Incorrect 23 ms 63608 KB Output isn't correct
10 Incorrect 25 ms 64168 KB Output isn't correct
11 Incorrect 26 ms 64020 KB Output isn't correct
12 Incorrect 27 ms 64384 KB Output isn't correct
13 Incorrect 26 ms 64360 KB Output isn't correct
14 Incorrect 25 ms 64348 KB Output isn't correct
15 Incorrect 34 ms 65236 KB Output isn't correct
16 Incorrect 34 ms 65144 KB Output isn't correct
17 Incorrect 36 ms 65108 KB Output isn't correct
18 Incorrect 31 ms 65300 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 78148 KB Output is correct
2 Incorrect 57 ms 68180 KB Output isn't correct
3 Incorrect 52 ms 78924 KB Output isn't correct
4 Incorrect 64 ms 70640 KB Output isn't correct
5 Correct 105 ms 75060 KB Output is correct
6 Incorrect 603 ms 87152 KB Output isn't correct
7 Correct 29 ms 78928 KB Output is correct
8 Correct 30 ms 78152 KB Output is correct
9 Incorrect 24 ms 63224 KB Output isn't correct
10 Correct 24 ms 63176 KB Output is correct
11 Correct 29 ms 78520 KB Output is correct
12 Correct 23 ms 63828 KB Output is correct
13 Incorrect 52 ms 68124 KB Output isn't correct
14 Incorrect 42 ms 66776 KB Output isn't correct
15 Correct 37 ms 67216 KB Output is correct
16 Incorrect 39 ms 64832 KB Output isn't correct
17 Incorrect 63 ms 71108 KB Output isn't correct
18 Correct 70 ms 71136 KB Output is correct
19 Incorrect 61 ms 70668 KB Output isn't correct
20 Incorrect 33 ms 70168 KB Output isn't correct
21 Incorrect 41 ms 75356 KB Output isn't correct
22 Correct 103 ms 75060 KB Output is correct
23 Incorrect 47 ms 73076 KB Output isn't correct
24 Correct 113 ms 75476 KB Output is correct
25 Correct 306 ms 78984 KB Output is correct
26 Correct 513 ms 127196 KB Output is correct
27 Runtime error 662 ms 223544 KB Execution killed with signal 11
28 Incorrect 608 ms 87180 KB Output isn't correct
29 Runtime error 663 ms 173532 KB Execution killed with signal 11
30 Runtime error 656 ms 186740 KB Execution killed with signal 11
31 Incorrect 377 ms 76016 KB Output isn't correct
32 Runtime error 566 ms 184984 KB Execution killed with signal 11