oj.uz

Submission #715018

# Submission time Handle Problem Language Result Execution time Memory
715018 2023-03-25T20:19:44 Z mariacichosz Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 698 ms 140892 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define sz size
#define st first
#define nd second

const int N = 4010;
const int inf = 1e9 + 3;

int h, w;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int dis[N][N];
bool vis[N][N];
char tab[N][N];

int ans;

void bfs(int x = 1, int y = 1){
    deque<pii> q;
    vis[x][y] = 1;
    dis[x][y] = 1;
    q.push_front({x, y});
    while (!q.empty()){
        auto v = q.front();
        q.pop_front();
        int sx = v.st, sy = v.nd;
        ans = max(dis[sx][sy], ans);
        for (int i = 0; i < 4; i ++){
            int nx = sx + dx[i], ny = sy + dy[i];
            if (nx < 1 || ny < 1 || nx > h || ny > w) continue;
            if (vis[nx][ny]) continue;
            if (tab[nx][ny] == '.') continue;
            if (tab[nx][ny] == tab[sx][sy]){
                dis[nx][ny] = dis[sx][sy];
                vis[nx][ny] = 1;
                q.push_front({nx, ny});
            }
            if (tab[nx][ny] != tab[sx][sy]){
                dis[nx][ny] = dis[sx][sy] + 1;
                vis[nx][ny] = 1;
                q.push_back({nx, ny});
            }
        }
    }
}

void cl(){
    for (int i = 0; i < N; i ++){
        for (int j = 0; j < N; j ++){
            dis[i][j] = inf;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cl();
    
    cin >> h >> w;
    for (int i = 1; i <= h; i ++){
        for (int j = 1; j <= w; j ++){
            cin >> tab[i][j];
        }
    }
    bfs();
    cout << ans << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 67152 KB Output is correct
2 Correct 29 ms 63300 KB Output is correct
3 Correct 29 ms 63576 KB Output is correct
4 Correct 37 ms 67280 KB Output is correct
5 Correct 32 ms 65468 KB Output is correct
6 Correct 29 ms 63340 KB Output is correct
7 Correct 29 ms 63608 KB Output is correct
8 Correct 30 ms 63668 KB Output is correct
9 Correct 30 ms 64036 KB Output is correct
10 Correct 31 ms 65124 KB Output is correct
11 Correct 31 ms 64900 KB Output is correct
12 Correct 37 ms 65572 KB Output is correct
13 Correct 32 ms 65532 KB Output is correct
14 Correct 34 ms 65488 KB Output is correct
15 Correct 41 ms 67088 KB Output is correct
16 Correct 49 ms 67148 KB Output is correct
17 Correct 45 ms 66928 KB Output is correct
18 Correct 37 ms 67212 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 93212 KB Output is correct
2 Correct 81 ms 73080 KB Output is correct
3 Correct 326 ms 94576 KB Output is correct
4 Correct 113 ms 78008 KB Output is correct
5 Correct 231 ms 86852 KB Output is correct
6 Correct 698 ms 108376 KB Output is correct
7 Correct 45 ms 94732 KB Output is correct
8 Correct 43 ms 93200 KB Output is correct
9 Correct 30 ms 63348 KB Output is correct
10 Correct 30 ms 63284 KB Output is correct
11 Correct 44 ms 94008 KB Output is correct
12 Correct 30 ms 64432 KB Output is correct
13 Correct 75 ms 72992 KB Output is correct
14 Correct 57 ms 70316 KB Output is correct
15 Correct 55 ms 71080 KB Output is correct
16 Correct 49 ms 66408 KB Output is correct
17 Correct 149 ms 79076 KB Output is correct
18 Correct 125 ms 78944 KB Output is correct
19 Correct 117 ms 78000 KB Output is correct
20 Correct 103 ms 77108 KB Output is correct
21 Correct 207 ms 87524 KB Output is correct
22 Correct 224 ms 86856 KB Output is correct
23 Correct 264 ms 83020 KB Output is correct
24 Correct 225 ms 87596 KB Output is correct
25 Correct 537 ms 94584 KB Output is correct
26 Correct 507 ms 140892 KB Output is correct
27 Correct 597 ms 121468 KB Output is correct
28 Correct 697 ms 108256 KB Output is correct
29 Correct 698 ms 106644 KB Output is correct
30 Correct 642 ms 111952 KB Output is correct
31 Correct 529 ms 88808 KB Output is correct
32 Correct 543 ms 110092 KB Output is correct