oj.uz

Submission #1101660

# Submission time Handle Problem Language Result Execution time Memory
1101660 2024-10-16T14:35:05 Z vanea Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 679 ms 177732 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 4e3+10;

vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1};

bool vis[mxN][mxN];
int h, w;

bool valid(int a, int b) {
    return (a >= 0 && a < h && b >= 0 && b < w && !vis[a][b]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> h >> w;
    int ans = 0;
    vector<string> v(h);
    for(int i = 0; i < h; i++) {
        cin >> v[i];
    }
    deque<array<int, 3>> q;
    q.push_back({1, 0, 0});
    while(!q.empty()) {
        int curr = q.front()[0], x = q.front()[1], y = q.front()[2];
        ans = max(ans, curr);
        vis[x][y] = true;
        q.pop_front();
        for(int k = 0; k < 4; k++) {
            int a = x+xy[k], b = y+yx[k];
            if(valid(a, b) && v[a][b] != '.') {
                if(v[a][b] == v[x][y]) q.push_front({curr, a, b});
                else q.push_back({curr+1, a, b});
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2896 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 8 ms 3244 KB Output is correct
5 Correct 3 ms 1616 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 3 ms 1292 KB Output is correct
12 Correct 6 ms 1616 KB Output is correct
13 Correct 4 ms 1616 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Correct 13 ms 2640 KB Output is correct
16 Correct 16 ms 2908 KB Output is correct
17 Correct 9 ms 2640 KB Output is correct
18 Correct 7 ms 3068 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15440 KB Output is correct
2 Correct 40 ms 7088 KB Output is correct
3 Correct 168 ms 33968 KB Output is correct
4 Correct 43 ms 11856 KB Output is correct
5 Correct 116 ms 21840 KB Output is correct
6 Correct 669 ms 81040 KB Output is correct
7 Correct 11 ms 16208 KB Output is correct
8 Correct 10 ms 15456 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 1 ms 508 KB Output is correct
11 Correct 10 ms 15952 KB Output is correct
12 Correct 1 ms 1016 KB Output is correct
13 Correct 38 ms 7104 KB Output is correct
14 Correct 22 ms 5068 KB Output is correct
15 Correct 10 ms 5456 KB Output is correct
16 Correct 20 ms 2792 KB Output is correct
17 Correct 94 ms 12776 KB Output is correct
18 Correct 40 ms 12372 KB Output is correct
19 Correct 39 ms 11856 KB Output is correct
20 Correct 42 ms 10832 KB Output is correct
21 Correct 104 ms 22608 KB Output is correct
22 Correct 108 ms 22056 KB Output is correct
23 Correct 192 ms 18940 KB Output is correct
24 Correct 85 ms 22400 KB Output is correct
25 Correct 212 ms 33864 KB Output is correct
26 Correct 431 ms 177732 KB Output is correct
27 Correct 511 ms 113632 KB Output is correct
28 Correct 679 ms 81048 KB Output is correct
29 Correct 660 ms 78800 KB Output is correct
30 Correct 606 ms 98060 KB Output is correct
31 Correct 608 ms 25928 KB Output is correct
32 Correct 462 ms 104664 KB Output is correct