oj.uz

Submission #966228

# Submission time Handle Problem Language Result Execution time Memory
966228 2024-04-19T14:38:04 Z Pring Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 313 ms 130208 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] = 1;
    dq.push_back(mp(srx, sry));
    while (dq.size()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        PUSH(x, y, 1, 0);
        PUSH(x, y, -1, 0);
        PUSH(x, y, 0, 1);
        PUSH(x, y, 0, -1);
    }
}

void miku() {
    cin >> n >> m;
    FOR(i, 1, n + 1) {
        cin >> s[i];
        s[i] = '.' + s[i] + '.';
    }
    s[0] = string(m + 2, '.');
    s[n + 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 << '\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 6 ms 9308 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 4 ms 9308 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2904 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 4696 KB Output is correct
11 Correct 1 ms 4820 KB Output is correct
12 Correct 3 ms 7004 KB Output is correct
13 Correct 2 ms 6748 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Correct 6 ms 9308 KB Output is correct
16 Correct 7 ms 9308 KB Output is correct
17 Correct 5 ms 9308 KB Output is correct
18 Correct 4 ms 9308 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 62188 KB Output is correct
2 Correct 22 ms 24156 KB Output is correct
3 Correct 115 ms 94720 KB Output is correct
4 Correct 43 ms 38748 KB Output is correct
5 Correct 69 ms 65628 KB Output is correct
6 Correct 313 ms 108204 KB Output is correct
7 Correct 9 ms 62300 KB Output is correct
8 Correct 8 ms 62184 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 8 ms 62184 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Correct 24 ms 24152 KB Output is correct
14 Correct 16 ms 16860 KB Output is correct
15 Correct 11 ms 19036 KB Output is correct
16 Correct 11 ms 8156 KB Output is correct
17 Correct 57 ms 41564 KB Output is correct
18 Correct 39 ms 41304 KB Output is correct
19 Correct 45 ms 38744 KB Output is correct
20 Correct 35 ms 36188 KB Output is correct
21 Correct 84 ms 68436 KB Output is correct
22 Correct 69 ms 65620 KB Output is correct
23 Correct 110 ms 56920 KB Output is correct
24 Correct 77 ms 67676 KB Output is correct
25 Correct 244 ms 94808 KB Output is correct
26 Correct 171 ms 130208 KB Output is correct
27 Correct 231 ms 121088 KB Output is correct
28 Correct 308 ms 108260 KB Output is correct
29 Correct 302 ms 106696 KB Output is correct
30 Correct 277 ms 111164 KB Output is correct
31 Correct 244 ms 72536 KB Output is correct
32 Correct 199 ms 109836 KB Output is correct