oj.uz

Submission #504916

# Submission time Handle Problem Language Result Execution time Memory
504916 2022-01-10T10:10:12 Z shubham20_03 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 557 ms 235976 KB 
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define deb(x) cout<<#x<<'='<<x<<'\n';
#define deb2(x,y) cout<<#x<<'='<<x<<", "<<#y<<'='<<y<<'\n';
#define int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
const long double PI = acos(-1);
const int mod = 1e9 + 7, inf = 1e10;
const int D = 4010;

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

int n, m;
string a[D];
int d[D][D];

void solve_test() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    deque<pii> q;
    q.pb({0, 0});
    d[0][0] = 1;

    int ans = 1;
    while (!q.empty()) {
        pii u = q.front();
        int ux = u.f, uy = u.s;
        q.pop_front();

        ans = max(ans, d[ux][uy]);

        for (int i = 0; i < 4; i++) {
            int vx = ux + dx[i];
            int vy = uy + dy[i];

            if (vx<0 or vx >= n or vy<0 or vy >= m)
                continue;

            if (a[vx][vy] == '.')
                continue;

            int wt = (a[ux][uy] != a[vx][vy]);
            if (d[vx][vy] == 0) {
                d[vx][vy] = d[ux][uy] + wt;
                if (wt) q.pb({vx, vy});
                else q.push_front({vx, vy});
            }
        }
    }

    cout << ans << '\n';
}

signed main() {
    fastio

    solve_test();

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4892 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 560 KB Output is correct
4 Correct 7 ms 4296 KB Output is correct
5 Correct 3 ms 2244 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 828 KB Output is correct
10 Correct 3 ms 1736 KB Output is correct
11 Correct 3 ms 1764 KB Output is correct
12 Correct 4 ms 2440 KB Output is correct
13 Correct 3 ms 2252 KB Output is correct
14 Correct 2 ms 2312 KB Output is correct
15 Correct 9 ms 4512 KB Output is correct
16 Correct 10 ms 4884 KB Output is correct
17 Correct 7 ms 4548 KB Output is correct
18 Correct 7 ms 4292 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16116 KB Output is correct
2 Correct 32 ms 15128 KB Output is correct
3 Correct 156 ms 90256 KB Output is correct
4 Correct 68 ms 43072 KB Output is correct
5 Correct 135 ms 69140 KB Output is correct
6 Correct 557 ms 184272 KB Output is correct
7 Correct 10 ms 16844 KB Output is correct
8 Correct 9 ms 16100 KB Output is correct
9 Correct 2 ms 968 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 9 ms 16464 KB Output is correct
12 Correct 1 ms 1228 KB Output is correct
13 Correct 31 ms 15132 KB Output is correct
14 Correct 19 ms 9824 KB Output is correct
15 Correct 18 ms 14252 KB Output is correct
16 Correct 15 ms 6484 KB Output is correct
17 Correct 81 ms 32984 KB Output is correct
18 Correct 73 ms 47736 KB Output is correct
19 Correct 63 ms 42984 KB Output is correct
20 Correct 43 ms 27068 KB Output is correct
21 Correct 100 ms 61184 KB Output is correct
22 Correct 136 ms 69184 KB Output is correct
23 Correct 152 ms 56152 KB Output is correct
24 Correct 102 ms 59316 KB Output is correct
25 Correct 395 ms 156244 KB Output is correct
26 Correct 347 ms 235976 KB Output is correct
27 Correct 439 ms 223160 KB Output is correct
28 Correct 555 ms 182076 KB Output is correct
29 Correct 534 ms 182436 KB Output is correct
30 Correct 490 ms 189372 KB Output is correct
31 Correct 420 ms 115300 KB Output is correct
32 Correct 400 ms 195360 KB Output is correct