oj.uz

Submission #797533

# Submission time Handle Problem Language Result Execution time Memory
797533 2023-07-29T14:59:29 Z bonk Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 923 ms 104704 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 4002;
char grid[N][N];
int vis[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
int n, m;

bool ok(int x, int y){
    return (1 <= x && x <= n && 1 <= y && y <= m && vis[x][y] == -1);
}

int bfs(int sx, int sy){
    int ret = 1;
    queue<pair<int, int>>q, tmp; 
    q.emplace(sx, sy);
    vis[sx][sy] = 1;

    while(!q.empty()){
        auto [x, y] = q.front(); q.pop();
        ret = max(ret, vis[x][y]);
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(ok(nx, ny)){
                if(grid[nx][ny] == grid[x][y]){
                    q.emplace(nx, ny);
                    vis[nx][ny] = vis[x][y];
                } else if(grid[nx][ny] != '.'){
                    tmp.emplace(nx, ny);
                    vis[nx][ny] = vis[x][y] + 1;
                }
            }
        }

        if(q.empty()){
            while(!tmp.empty()){
                q.push(tmp.front());
                tmp.pop();
            }
        }
    }

    return ret;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(vis, -1, sizeof(vis));
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            cin >> grid[i][j];
    }

    cout << bfs(1, 1) << '\n';

    return 0;
}

Compilation message

tracks.cpp: In function 'int bfs(int, int)':
tracks.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         auto [x, y] = q.front(); q.pop();
      |              ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65240 KB Output is correct
2 Correct 20 ms 62976 KB Output is correct
3 Correct 21 ms 63196 KB Output is correct
4 Correct 28 ms 65236 KB Output is correct
5 Correct 24 ms 64184 KB Output is correct
6 Correct 22 ms 62992 KB Output is correct
7 Correct 22 ms 63192 KB Output is correct
8 Correct 21 ms 63248 KB Output is correct
9 Correct 21 ms 63344 KB Output is correct
10 Correct 23 ms 63980 KB Output is correct
11 Correct 23 ms 63800 KB Output is correct
12 Correct 26 ms 64164 KB Output is correct
13 Correct 23 ms 64204 KB Output is correct
14 Correct 25 ms 64156 KB Output is correct
15 Correct 32 ms 65184 KB Output is correct
16 Correct 33 ms 65108 KB Output is correct
17 Correct 31 ms 65012 KB Output is correct
18 Correct 29 ms 65116 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 77976 KB Output is correct
2 Correct 68 ms 69332 KB Output is correct
3 Correct 281 ms 94300 KB Output is correct
4 Correct 94 ms 74048 KB Output is correct
5 Correct 193 ms 83540 KB Output is correct
6 Correct 890 ms 104704 KB Output is correct
7 Correct 28 ms 78692 KB Output is correct
8 Correct 28 ms 78012 KB Output is correct
9 Correct 28 ms 63016 KB Output is correct
10 Correct 24 ms 63016 KB Output is correct
11 Correct 28 ms 78420 KB Output is correct
12 Correct 24 ms 63572 KB Output is correct
13 Correct 67 ms 69420 KB Output is correct
14 Correct 47 ms 67412 KB Output is correct
15 Correct 42 ms 67880 KB Output is correct
16 Correct 43 ms 65168 KB Output is correct
17 Correct 143 ms 74812 KB Output is correct
18 Correct 101 ms 74724 KB Output is correct
19 Correct 91 ms 74020 KB Output is correct
20 Correct 82 ms 73180 KB Output is correct
21 Correct 180 ms 84208 KB Output is correct
22 Correct 199 ms 83624 KB Output is correct
23 Correct 269 ms 80392 KB Output is correct
24 Correct 185 ms 84092 KB Output is correct
25 Correct 447 ms 94296 KB Output is correct
26 Correct 467 ms 88732 KB Output is correct
27 Correct 620 ms 96044 KB Output is correct
28 Correct 923 ms 104620 KB Output is correct
29 Correct 872 ms 102832 KB Output is correct
30 Correct 769 ms 101532 KB Output is correct
31 Correct 669 ms 86012 KB Output is correct
32 Correct 618 ms 95164 KB Output is correct