oj.uz

Submission #746783

# Submission time Handle Problem Language Result Execution time Memory
746783 2023-05-23T05:54:27 Z Github Tracks in the Snow (BOI13_tracks) C++14
31.7708 / 100
 687 ms 239208 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, -1, 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] == -1){
                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 31 ms 65356 KB Output isn't correct
2 Correct 22 ms 63268 KB Output is correct
3 Incorrect 25 ms 63388 KB Output isn't correct
4 Incorrect 30 ms 65356 KB Output isn't correct
5 Incorrect 26 ms 64444 KB Output isn't correct
6 Correct 25 ms 63308 KB Output is correct
7 Incorrect 23 ms 63444 KB Output isn't correct
8 Incorrect 25 ms 63372 KB Output isn't correct
9 Incorrect 27 ms 63644 KB Output isn't correct
10 Incorrect 27 ms 64212 KB Output isn't correct
11 Incorrect 27 ms 64212 KB Output isn't correct
12 Incorrect 28 ms 64460 KB Output isn't correct
13 Incorrect 27 ms 64456 KB Output isn't correct
14 Incorrect 25 ms 64400 KB Output isn't correct
15 Incorrect 32 ms 65440 KB Output isn't correct
16 Incorrect 32 ms 65380 KB Output isn't correct
17 Incorrect 29 ms 65328 KB Output isn't correct
18 Incorrect 29 ms 65356 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78180 KB Output is correct
2 Incorrect 58 ms 69588 KB Output isn't correct
3 Incorrect 68 ms 94640 KB Output isn't correct
4 Incorrect 65 ms 74332 KB Output isn't correct
5 Correct 110 ms 83924 KB Output is correct
6 Incorrect 631 ms 102860 KB Output isn't correct
7 Correct 37 ms 78876 KB Output is correct
8 Correct 38 ms 78260 KB Output is correct
9 Incorrect 27 ms 63332 KB Output isn't correct
10 Correct 28 ms 63232 KB Output is correct
11 Correct 37 ms 78664 KB Output is correct
12 Correct 26 ms 63792 KB Output is correct
13 Incorrect 56 ms 69708 KB Output isn't correct
14 Incorrect 41 ms 67704 KB Output isn't correct
15 Correct 40 ms 68100 KB Output is correct
16 Incorrect 38 ms 65448 KB Output isn't correct
17 Incorrect 71 ms 75144 KB Output isn't correct
18 Correct 79 ms 74924 KB Output is correct
19 Incorrect 75 ms 74340 KB Output isn't correct
20 Incorrect 37 ms 73588 KB Output isn't correct
21 Incorrect 46 ms 84540 KB Output isn't correct
22 Correct 107 ms 83960 KB Output is correct
23 Incorrect 55 ms 80656 KB Output isn't correct
24 Correct 125 ms 84396 KB Output is correct
25 Correct 317 ms 94652 KB Output is correct
26 Correct 505 ms 139160 KB Output is correct
27 Runtime error 687 ms 239208 KB Execution killed with signal 11
28 Incorrect 622 ms 102884 KB Output isn't correct
29 Runtime error 669 ms 189088 KB Execution killed with signal 11
30 Runtime error 687 ms 202052 KB Execution killed with signal 11
31 Incorrect 394 ms 85964 KB Output isn't correct
32 Runtime error 574 ms 200636 KB Execution killed with signal 11