oj.uz

Submission #1100382

# Submission time Handle Problem Language Result Execution time Memory
1100382 2024-10-13T16:26:06 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 768 ms 221528 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(a) (int)(a).size()
#define el '\n'
#define F first
#define S second
#define For(i, a, b) for (int i = (a); i <= (int)(b); i++)
#define Rof(i, a, b) for (int i = (a); i >= (int)(b); i--)
#define Fore(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)

using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vii = vector<pii>;

//*** START CODING ***//

const long long oo = 2e18, mod = 1e9 + 7;
const int ms = 2e5 + 5;
int n, m;

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

void solve() {
    cin >> n >> m;
    vvc a(n, vc(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    vvi dist(n, vi(m, 0));
    deque<pii> q;
    q.push_back({0, 0});
    int ans = 0;
    dist[0][0] = 1;

    while (!q.empty()) {
        pii cur = q.front();
        q.pop_front();
        ans = max(ans, dist[cur.F][cur.S]);

        for (int i = 0; i < 4; i++) {
            int nx = cur.F + dx[i];
            int ny = cur.S + dy[i];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m) continue;
            if (a[nx][ny] == '.') continue;
            if (dist[nx][ny] != 0) continue;

            if (a[cur.F][cur.S] == a[nx][ny]) {
                dist[nx][ny] = dist[cur.F][cur.S];
                q.push_front({nx, ny});
            } else {
                dist[nx][ny] = dist[cur.F][cur.S] + 1;
                q.push_back({nx, ny});
            }
        }
    }
    cout << ans << el;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2900 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 7 ms 2424 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 2 ms 864 KB Output is correct
12 Correct 4 ms 1364 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 3 ms 1108 KB Output is correct
15 Correct 10 ms 2900 KB Output is correct
16 Correct 11 ms 2900 KB Output is correct
17 Correct 9 ms 2644 KB Output is correct
18 Correct 6 ms 2388 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1272 KB Output is correct
2 Correct 48 ms 15872 KB Output is correct
3 Correct 289 ms 157260 KB Output is correct
4 Correct 90 ms 37196 KB Output is correct
5 Correct 217 ms 88652 KB Output is correct
6 Correct 657 ms 183052 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 3 ms 832 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 2 ms 1108 KB Output is correct
12 Correct 1 ms 696 KB Output is correct
13 Correct 45 ms 15696 KB Output is correct
14 Correct 24 ms 9464 KB Output is correct
15 Correct 21 ms 10068 KB Output is correct
16 Correct 19 ms 6740 KB Output is correct
17 Correct 139 ms 40332 KB Output is correct
18 Correct 84 ms 39596 KB Output is correct
19 Correct 96 ms 37068 KB Output is correct
20 Correct 78 ms 34124 KB Output is correct
21 Correct 191 ms 91628 KB Output is correct
22 Correct 214 ms 88600 KB Output is correct
23 Correct 250 ms 76364 KB Output is correct
24 Correct 191 ms 89420 KB Output is correct
25 Correct 329 ms 157364 KB Output is correct
26 Correct 522 ms 221528 KB Output is correct
27 Correct 631 ms 196672 KB Output is correct
28 Correct 768 ms 183000 KB Output is correct
29 Correct 700 ms 180724 KB Output is correct
30 Correct 693 ms 180436 KB Output is correct
31 Correct 447 ms 101604 KB Output is correct
32 Correct 536 ms 183032 KB Output is correct