oj.uz

Submission #530288

# Submission time Handle Problem Language Result Execution time Memory
530288 2022-02-25T02:03:16 Z raypeng1729 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 763 ms 220776 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
const int N = 2e5 + 5, MOD = 1e9 + 7, INF = 1e9;
#define X first
#define Y second
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> dis(n, vector<int>(m, INF));
    vector<vector<char>> c(n, (vector<char>(m)));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> c[i][j];
        }   
    }
    deque<pair<int, int>> dq;
    int ans = 0;
    dq.push_back({0, 0});
    dis[0][0] = 1;
    auto check = [&](int i, int j, int x, int y){
        if(c[i][j] == '.' || dis[i][j] != INF) return;
        if(c[i][j] == c[x][y]) dis[i][j] = dis[x][y], dq.push_front({i, j});
        else dis[i][j] = dis[x][y] + 1, dq.push_back({i, j});
    };
    while(dq.size()){
        auto i = dq.front(); dq.pop_front();
        int I = i.X, J = i.Y;
        if(I < n - 1) check(I + 1, J, I, J);
        if(I) check(I - 1, J, I, J);
        if(J < m - 1)check(I, J + 1, I, J);
        if(J) check(I, J - 1, I, J);
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        if(dis[i][j] != INF) ans = max(ans, dis[i][j]);
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2756 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 7 ms 2228 KB Output is correct
5 Correct 3 ms 1096 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 3 ms 960 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 6 ms 1220 KB Output is correct
13 Correct 3 ms 1092 KB Output is correct
14 Correct 4 ms 1140 KB Output is correct
15 Correct 10 ms 2772 KB Output is correct
16 Correct 12 ms 2764 KB Output is correct
17 Correct 9 ms 2620 KB Output is correct
18 Correct 7 ms 2252 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 972 KB Output is correct
2 Correct 53 ms 15672 KB Output is correct
3 Correct 375 ms 157272 KB Output is correct
4 Correct 103 ms 37136 KB Output is correct
5 Correct 237 ms 88508 KB Output is correct
6 Correct 763 ms 184436 KB Output is correct
7 Correct 2 ms 972 KB Output is correct
8 Correct 2 ms 1092 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 1228 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 59 ms 15684 KB Output is correct
14 Correct 28 ms 9156 KB Output is correct
15 Correct 26 ms 10180 KB Output is correct
16 Correct 23 ms 6604 KB Output is correct
17 Correct 144 ms 40176 KB Output is correct
18 Correct 152 ms 39512 KB Output is correct
19 Correct 101 ms 37124 KB Output is correct
20 Correct 83 ms 34040 KB Output is correct
21 Correct 214 ms 91652 KB Output is correct
22 Correct 233 ms 88588 KB Output is correct
23 Correct 265 ms 76272 KB Output is correct
24 Correct 220 ms 89492 KB Output is correct
25 Correct 675 ms 157304 KB Output is correct
26 Correct 532 ms 220776 KB Output is correct
27 Correct 662 ms 210472 KB Output is correct
28 Correct 756 ms 184532 KB Output is correct
29 Correct 732 ms 181032 KB Output is correct
30 Correct 749 ms 189620 KB Output is correct
31 Correct 522 ms 101676 KB Output is correct
32 Correct 620 ms 187872 KB Output is correct