oj.uz

Submission #966226

# Submission time Handle Problem Language Result Execution time Memory
966226 2024-04-19T14:35:22 Z Pring Tracks in the Snow (BOI13_tracks) C++17
84.6875 / 100
 355 ms 142164 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 4005;
int n, m;
string s[MXN];
int dis[MXN][MXN];

void BFS(int srx, int sry) {
    deque<pii> dq;
    FOR(i, 0, n + 2) FOR(j, 0, m + 2) dis[i][j] = -1;
    auto PUSH = [&](int x, int y, int dx, int dy) -> void {
        dx += x;
        dy += y;
        if (s[dx][dy] == '.') return;
        if (dis[dx][dy] != -1) return;
        if (s[x][y] == s[dx][dy]) {
            dis[dx][dy] = dis[x][y];
            dq.push_front(mp(dx, dy));
        } else {
            dis[dx][dy] = dis[x][y] + 1;
            dq.push_back(mp(dx, dy));
        }
    };
    dis[srx][sry] = 0;
    dq.push_back(mp(srx, sry));
    while (dq.size()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        PUSH(x, y, 0, 1);
        PUSH(x, y, 0, -1);
        PUSH(x, y, 1, 0);
        PUSH(x, y, -1, 0);
    }
}

void miku() {
    cin >> n >> m;
    FOR(i, 1, n + 1) {
        cin >> s[i];
        s[i] = '.' + s[i] + '.';
    }
    s[0] = string(m + 2, '.');
    s[m + 1] = string(m + 2, '.');
    BFS(1, 1);
    int ans = 0;
    FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
        if (s[i][j] == '.') continue;
        ans = max(ans, dis[i][j]);
    }
    cout << ans + 1 << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9564 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 3 ms 6848 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 4700 KB Output is correct
11 Correct 2 ms 4700 KB Output is correct
12 Correct 4 ms 7100 KB Output is correct
13 Correct 2 ms 7004 KB Output is correct
14 Correct 2 ms 7008 KB Output is correct
15 Correct 6 ms 9564 KB Output is correct
16 Correct 7 ms 9564 KB Output is correct
17 Correct 6 ms 9564 KB Output is correct
18 Correct 3 ms 9444 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 62032 KB Output isn't correct
2 Correct 24 ms 25832 KB Output is correct
3 Correct 131 ms 110156 KB Output is correct
4 Correct 45 ms 42320 KB Output is correct
5 Correct 71 ms 74212 KB Output is correct
6 Correct 355 ms 123616 KB Output is correct
7 Incorrect 8 ms 62296 KB Output isn't correct
8 Incorrect 7 ms 62044 KB Output isn't correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 8 ms 62084 KB Output isn't correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 24 ms 25788 KB Output is correct
14 Correct 14 ms 17500 KB Output is correct
15 Correct 10 ms 20060 KB Output is correct
16 Correct 12 ms 8540 KB Output is correct
17 Correct 66 ms 45404 KB Output is correct
18 Correct 43 ms 45392 KB Output is correct
19 Correct 53 ms 42464 KB Output is correct
20 Correct 39 ms 39512 KB Output is correct
21 Incorrect 85 ms 77432 KB Output isn't correct
22 Correct 70 ms 74324 KB Output is correct
23 Incorrect 121 ms 64596 KB Output isn't correct
24 Incorrect 78 ms 76708 KB Output isn't correct
25 Correct 256 ms 110160 KB Output is correct
26 Correct 344 ms 142164 KB Output is correct
27 Correct 286 ms 128848 KB Output is correct
28 Correct 354 ms 123596 KB Output is correct
29 Correct 354 ms 121296 KB Output is correct
30 Correct 332 ms 125652 KB Output is correct
31 Correct 263 ms 82600 KB Output is correct
32 Correct 297 ms 127220 KB Output is correct