oj.uz

Submission #881452

# Submission time Handle Problem Language Result Execution time Memory
881452 2023-12-01T09:01:15 Z noompty Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 577 ms 138596 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <array>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif
 
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
 
int h, w, dist[4005][4005], ans;
char grid[4005][4005];
deque<pair<int, int>> q;
 
bool valid(int x, int y) {
    if (x < 0 || x >= h || y < 0 || y >= w) return false;
    if (grid[x][y] == '.') return false;
    return true;
}
 
void bfs(int sr, int sc) {
    fill(&dist[0][0], &dist[0][0] + sizeof(dist) / sizeof(dist[0][0]), 2e9);
    dist[sr][sc] = 1;
    q.push_back({sr, sc});
    while (!q.empty()) {
        int cr = q.front().f, cc = q.front().s;
        q.pop_front();
        for (int i = 0, nr, nc; i < 4; i++) {
            nr = cr + dx[i];
            nc = cc + dy[i];
            if (valid(nr, nc)) {
                if (grid[nr][nc] == grid[cr][cc]) {
                    if (dist[nr][nc] > dist[cr][cc]) {
                        dist[nr][nc] = dist[cr][cc];
                        q.push_front({nr, nc});
                    }
                } else {
                    if (dist[nr][nc] > dist[cr][cc] + 1) {
                        dist[nr][nc] = dist[cr][cc] + 1;
                        q.push_back({nr, nc});
                    }
                }
            }
        }
    }
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
        }
    }
 
    bfs(0, 0);
 
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (dist[i][j] < 2e9) {
                ans = max(ans, dist[i][j]);
            }
        }
    }
 
    cout << ans << "\n";
 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 66904 KB Output is correct
2 Correct 17 ms 64344 KB Output is correct
3 Correct 18 ms 66648 KB Output is correct
4 Correct 27 ms 66900 KB Output is correct
5 Correct 19 ms 66644 KB Output is correct
6 Correct 17 ms 64348 KB Output is correct
7 Correct 17 ms 66388 KB Output is correct
8 Correct 17 ms 66396 KB Output is correct
9 Correct 18 ms 66512 KB Output is correct
10 Correct 20 ms 66496 KB Output is correct
11 Correct 18 ms 66652 KB Output is correct
12 Correct 21 ms 66652 KB Output is correct
13 Correct 19 ms 66644 KB Output is correct
14 Correct 19 ms 66560 KB Output is correct
15 Correct 28 ms 66652 KB Output is correct
16 Correct 29 ms 66652 KB Output is correct
17 Correct 28 ms 66648 KB Output is correct
18 Correct 26 ms 66928 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 78836 KB Output is correct
2 Correct 60 ms 72348 KB Output is correct
3 Correct 273 ms 91400 KB Output is correct
4 Correct 83 ms 76120 KB Output is correct
5 Correct 185 ms 84416 KB Output is correct
6 Correct 572 ms 106164 KB Output is correct
7 Correct 22 ms 79196 KB Output is correct
8 Correct 19 ms 78896 KB Output is correct
9 Correct 19 ms 64340 KB Output is correct
10 Correct 23 ms 64340 KB Output is correct
11 Correct 24 ms 78932 KB Output is correct
12 Correct 18 ms 66572 KB Output is correct
13 Correct 56 ms 72084 KB Output is correct
14 Correct 40 ms 69444 KB Output is correct
15 Correct 36 ms 69456 KB Output is correct
16 Correct 37 ms 67164 KB Output is correct
17 Correct 118 ms 76356 KB Output is correct
18 Correct 92 ms 76324 KB Output is correct
19 Correct 100 ms 76172 KB Output is correct
20 Correct 80 ms 75716 KB Output is correct
21 Correct 165 ms 84668 KB Output is correct
22 Correct 180 ms 84272 KB Output is correct
23 Correct 213 ms 81224 KB Output is correct
24 Correct 167 ms 84088 KB Output is correct
25 Correct 420 ms 91708 KB Output is correct
26 Correct 371 ms 138596 KB Output is correct
27 Correct 451 ms 121120 KB Output is correct
28 Correct 577 ms 106596 KB Output is correct
29 Correct 563 ms 102320 KB Output is correct
30 Correct 541 ms 111448 KB Output is correct
31 Correct 515 ms 86292 KB Output is correct
32 Correct 404 ms 106764 KB Output is correct