oj.uz

Submission #536621

# Submission time Handle Problem Language Result Execution time Memory
536621 2022-03-13T15:06:50 Z MohamedFaresNebili Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 873 ms 131088 KB 
#include <bits/stdc++.h>

        using namespace std;

        using ll = long long;
        using ii = pair<int, int>;
        using vi = vector<int>;
        using db = double;

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) x.begin(), x.end()
        #define lb lower_bound
        #define ub upper_bound

        const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0};

        int n, m, dis[4005][4005];
        char grid[4005][4005];

        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> m;
            for(int l = 0; l < n; l++)
                for(int i = 0; i < m; i++)
                    cin >> grid[l][i];
            dis[0][0] = 1; int res = 1;
            deque<ii> q; q.push_front({0, 0});
            while(!q.empty()) {
                ii a = q.front(); res = max(res, dis[a.ff][a.ss]); q.pop_front();
                for(int l = 0; l < 4; l++) {
                    int x = a.ff + nx[l], y = a.ss + ny[l];
                    if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '.' && dis[x][y] == 0) {
                        if(grid[x][y] == grid[a.ff][a.ss]) {
                            dis[x][y] = dis[a.ff][a.ss];
                            q.push_front({x, y});
                        }
                        else {
                            dis[x][y] = dis[a.ff][a.ss] + 1;
                            q.push_back({x, y});
                        }
                    }
                }
            }
            cout << res << "\n";
        }

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5332 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 12 ms 5204 KB Output is correct
5 Correct 4 ms 2900 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 3 ms 2400 KB Output is correct
11 Correct 3 ms 2132 KB Output is correct
12 Correct 6 ms 3028 KB Output is correct
13 Correct 3 ms 2900 KB Output is correct
14 Correct 5 ms 2896 KB Output is correct
15 Correct 14 ms 5280 KB Output is correct
16 Correct 16 ms 5320 KB Output is correct
17 Correct 11 ms 5204 KB Output is correct
18 Correct 10 ms 5140 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30804 KB Output is correct
2 Correct 55 ms 15032 KB Output is correct
3 Correct 364 ms 73400 KB Output is correct
4 Correct 100 ms 32752 KB Output is correct
5 Correct 220 ms 53296 KB Output is correct
6 Correct 835 ms 107636 KB Output is correct
7 Correct 16 ms 32212 KB Output is correct
8 Correct 18 ms 30804 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 16 ms 31572 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 68 ms 15108 KB Output is correct
14 Correct 36 ms 10316 KB Output is correct
15 Correct 31 ms 13100 KB Output is correct
16 Correct 26 ms 5652 KB Output is correct
17 Correct 137 ms 28744 KB Output is correct
18 Correct 124 ms 35648 KB Output is correct
19 Correct 142 ms 32592 KB Output is correct
20 Correct 86 ms 25640 KB Output is correct
21 Correct 209 ms 52424 KB Output is correct
22 Correct 242 ms 53384 KB Output is correct
23 Correct 257 ms 43820 KB Output is correct
24 Correct 231 ms 49720 KB Output is correct
25 Correct 548 ms 94300 KB Output is correct
26 Correct 865 ms 131088 KB Output is correct
27 Correct 805 ms 112524 KB Output is correct
28 Correct 827 ms 107500 KB Output is correct
29 Correct 846 ms 105204 KB Output is correct
30 Correct 869 ms 109844 KB Output is correct
31 Correct 555 ms 73432 KB Output is correct
32 Correct 873 ms 110320 KB Output is correct