oj.uz

Submission #883769

# Submission time Handle Problem Language Result Execution time Memory
883769 2023-12-06T01:38:38 Z Billy_Nguyen Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 627 ms 220932 KB 
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

#define x first
#define fastio()                 \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define y second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
int mod = 1e9 + 7;
int mod_inverse_2 = 500000004; // Modular inverse of 2 modulo (10^9 + 7), also
                               // the number has to be in long long otherwise
                               // if the number is int need to mutiply by 1LL
const int N = 100009;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
ll bound = 1e18;
ll H, W;
vector<vector<char>> grid;
vector<vector<ll>> depths;

void solve()
{
    cin >> H >> W;
    grid.resize(H + 1);
    depths.resize(H + 1);

    REP(i, 0, H + 1)
    {
        grid[i].resize(W + 1);
        depths[i].resize(W + 1, 0);
    }

    REP(i, 1, H + 1)
    {
        REP(j, 1, W + 1)
        {
            cin >> grid[i][j];
        }
    }

    deque<pair<ll, ll>> q;
    depths[1][1] = 1;
    q.push_back({1, 1});
    ll ans = 0;

    while (!q.empty())
    {
        pair<ll, ll> curr = q.front();
        q.pop_front();

        ans = max(ans, depths[curr.x][curr.y]);

        REP(k, 0, 4)
        {
            if (curr.x + dy[k] < 1 || curr.y + dx[k] < 1 ||
                curr.x + dy[k] > H || curr.y + dx[k] > W)
            {
                continue;
            }

            pair<ll, ll> nxt = {curr.x + dy[k], curr.y + dx[k]};

            if (grid[nxt.x][nxt.y] == '.')
            {
                continue;
            }

            if (depths[nxt.x][nxt.y] != 0)
            {
                continue;
            }

            if (grid[nxt.x][nxt.y] == grid[curr.x][curr.y])
            {
                    depths[nxt.x][nxt.y] = depths[curr.x][curr.y];
                    q.push_front(nxt);
            }
            else
            {
                    depths[nxt.x][nxt.y] = depths[curr.x][curr.y] + 1;
                    q.push_back(nxt);
            }
        }
    }

    cout << ans << "\n";
}

int main()
{
    fastio();
    solve();

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2908 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 2224 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 1112 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 5 ms 1528 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 9 ms 2944 KB Output is correct
16 Correct 10 ms 2908 KB Output is correct
17 Correct 8 ms 2652 KB Output is correct
18 Correct 6 ms 2376 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 44 ms 15716 KB Output is correct
3 Correct 297 ms 157500 KB Output is correct
4 Correct 80 ms 37208 KB Output is correct
5 Correct 171 ms 88532 KB Output is correct
6 Correct 627 ms 184544 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1236 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 43 ms 15708 KB Output is correct
14 Correct 23 ms 9228 KB Output is correct
15 Correct 20 ms 10072 KB Output is correct
16 Correct 19 ms 6744 KB Output is correct
17 Correct 113 ms 40276 KB Output is correct
18 Correct 90 ms 39508 KB Output is correct
19 Correct 80 ms 37200 KB Output is correct
20 Correct 67 ms 34256 KB Output is correct
21 Correct 174 ms 91728 KB Output is correct
22 Correct 169 ms 88660 KB Output is correct
23 Correct 219 ms 76628 KB Output is correct
24 Correct 165 ms 89424 KB Output is correct
25 Correct 453 ms 157428 KB Output is correct
26 Correct 399 ms 220932 KB Output is correct
27 Correct 497 ms 200516 KB Output is correct
28 Correct 618 ms 184432 KB Output is correct
29 Correct 609 ms 180672 KB Output is correct
30 Correct 572 ms 187036 KB Output is correct
31 Correct 434 ms 101824 KB Output is correct
32 Correct 453 ms 183028 KB Output is correct