oj.uz

Submission #533954

# Submission time Handle Problem Language Result Execution time Memory
533954 2022-03-07T18:01:45 Z AaronJ Tracks in the Snow (BOI13_tracks) C++
100 / 100
 943 ms 220784 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 13 ms 2748 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 8 ms 2232 KB Output is correct
5 Correct 3 ms 1092 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 960 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 6 ms 1216 KB Output is correct
13 Correct 3 ms 1100 KB Output is correct
14 Correct 3 ms 1100 KB Output is correct
15 Correct 11 ms 2776 KB Output is correct
16 Correct 11 ms 2844 KB Output is correct
17 Correct 10 ms 2680 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 2 ms 1088 KB Output is correct
2 Correct 55 ms 15792 KB Output is correct
3 Correct 379 ms 153732 KB Output is correct
4 Correct 108 ms 37060 KB Output is correct
5 Correct 243 ms 88560 KB Output is correct
6 Correct 787 ms 180984 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 632 KB Output is correct
11 Correct 2 ms 1100 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 51 ms 15680 KB Output is correct
14 Correct 29 ms 9188 KB Output is correct
15 Correct 27 ms 10040 KB Output is correct
16 Correct 25 ms 6628 KB Output is correct
17 Correct 136 ms 40100 KB Output is correct
18 Correct 132 ms 39504 KB Output is correct
19 Correct 109 ms 37060 KB Output is correct
20 Correct 92 ms 34076 KB Output is correct
21 Correct 218 ms 91572 KB Output is correct
22 Correct 249 ms 88616 KB Output is correct
23 Correct 252 ms 76248 KB Output is correct
24 Correct 222 ms 89412 KB Output is correct
25 Correct 681 ms 153980 KB Output is correct
26 Correct 543 ms 220784 KB Output is correct
27 Correct 710 ms 207432 KB Output is correct
28 Correct 866 ms 181556 KB Output is correct
29 Correct 943 ms 178852 KB Output is correct
30 Correct 896 ms 187676 KB Output is correct
31 Correct 671 ms 101672 KB Output is correct
32 Correct 706 ms 185524 KB Output is correct