oj.uz

Submission #920118

# Submission time Handle Problem Language Result Execution time Memory
920118 2024-02-02T04:54:58 Z thienbao1602 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 739 ms 164136 KB 
#include    <bits/stdc++.h>
#define SKY
#define ll long long
#define ld long double
#define MASK(x) (1LL << x)
#define sz(x) (int)x.size()
#define ii pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set0(d) memset(d, 0, sizeof(d))
using namespace std;

const int LOG = 20;
const int base = 311;
const ll inf = 1e18;
const int block = 400;
const ll MOD = 1e9 + 7;
const int mxN = 1e6 + 66;
const int mxN2D = 4e3 + 55;
const int x[] = {0, 1, 0, -1};
const int y[] = {1, 0, -1, 0};

int H, W;
char grid[mxN2D][mxN2D];

bool safe(int x, int y)
{
    return (x >= 0 && x < H && y >= 0 && y < W && grid[x][y] != '.');
}

void solve()
{
    cin >> H >> W;
    for (int r=0; r<H; r++)
    {
        for(int c=0; c<W; c++)
        {
            cin >> grid[r][c];
        }
    }

    deque<ii> pq;
    pq.push_back(mp(0, 0));
    vector<vector<int>> depth(H, vector<int>(W, 0));
    depth[0][0] = 1;

    int ans = 1;
    while(!pq.empty())
    {
        ii cell = pq.front();
        pq.pop_front();
        int u = cell.fi;
        int v = cell.se;

        ans = max(ans, depth[u][v]);
        for (int i=0; i<4; i++)
        {
            int ux = u + x[i];
            int vx = v + y[i];

            if (safe(ux, vx) && !depth[ux][vx])
            {
                depth[ux][vx] = depth[u][v] + (grid[ux][vx] != grid[u][v]);
                if (grid[ux][vx] == grid[u][v])
                {
                    pq.push_front(mp(ux, vx));
                } else
                {
                    pq.push_back(mp(ux, vx));
                }
            }
        }
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    #ifdef SKY
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    #endif //SKY
    solve();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3672 KB Output is correct
2 Correct 0 ms 548 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 3 ms 2904 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 2 ms 2904 KB Output is correct
11 Correct 2 ms 3160 KB Output is correct
12 Correct 5 ms 2904 KB Output is correct
13 Correct 3 ms 2904 KB Output is correct
14 Correct 3 ms 2904 KB Output is correct
15 Correct 9 ms 3676 KB Output is correct
16 Correct 11 ms 3672 KB Output is correct
17 Correct 8 ms 3416 KB Output is correct
18 Correct 6 ms 3672 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15704 KB Output is correct
2 Correct 43 ms 12892 KB Output is correct
3 Correct 323 ms 79236 KB Output is correct
4 Correct 81 ms 23376 KB Output is correct
5 Correct 209 ms 48280 KB Output is correct
6 Correct 739 ms 107700 KB Output is correct
7 Correct 4 ms 16472 KB Output is correct
8 Correct 3 ms 15704 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 5 ms 16216 KB Output is correct
12 Correct 1 ms 2648 KB Output is correct
13 Correct 42 ms 12972 KB Output is correct
14 Correct 26 ms 8328 KB Output is correct
15 Correct 20 ms 8540 KB Output is correct
16 Correct 20 ms 5208 KB Output is correct
17 Correct 113 ms 24824 KB Output is correct
18 Correct 90 ms 24568 KB Output is correct
19 Correct 81 ms 23376 KB Output is correct
20 Correct 72 ms 22356 KB Output is correct
21 Correct 192 ms 49536 KB Output is correct
22 Correct 204 ms 48208 KB Output is correct
23 Correct 222 ms 41552 KB Output is correct
24 Correct 177 ms 48464 KB Output is correct
25 Correct 523 ms 79216 KB Output is correct
26 Correct 659 ms 164136 KB Output is correct
27 Correct 671 ms 130368 KB Output is correct
28 Correct 739 ms 107656 KB Output is correct
29 Correct 729 ms 102320 KB Output is correct
30 Correct 719 ms 114896 KB Output is correct
31 Correct 484 ms 56144 KB Output is correct
32 Correct 669 ms 127344 KB Output is correct