oj.uz

Submission #881416

# Submission time Handle Problem Language Result Execution time Memory
881416 2023-12-01T08:41:06 Z noompty Tracks in the Snow (BOI13_tracks) C++17
75.9375 / 100
 2000 ms 95376 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];
queue<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({sr, sc});
    while (!q.empty()) {
        int cr = q.front().f, cc = q.front().s;
        q.pop();
        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({nr, nc});
                    }
                } else {
                    if (dist[nr][nc] > dist[cr][cc] + 1) {
                        dist[nr][nc] = dist[cr][cc] + 1;
                        q.push({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 213 ms 66900 KB Output is correct
2 Correct 12 ms 64348 KB Output is correct
3 Correct 13 ms 66396 KB Output is correct
4 Correct 32 ms 66652 KB Output is correct
5 Correct 26 ms 66652 KB Output is correct
6 Correct 12 ms 64344 KB Output is correct
7 Correct 13 ms 66396 KB Output is correct
8 Correct 13 ms 66384 KB Output is correct
9 Correct 13 ms 66396 KB Output is correct
10 Correct 18 ms 66620 KB Output is correct
11 Correct 15 ms 66652 KB Output is correct
12 Correct 56 ms 66716 KB Output is correct
13 Correct 22 ms 66652 KB Output is correct
14 Correct 27 ms 66552 KB Output is correct
15 Correct 108 ms 66868 KB Output is correct
16 Correct 206 ms 66904 KB Output is correct
17 Correct 116 ms 66896 KB Output is correct
18 Correct 32 ms 66652 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 78848 KB Output is correct
2 Correct 539 ms 72308 KB Output is correct
3 Execution timed out 2027 ms 94820 KB Time limit exceeded
4 Correct 1398 ms 76516 KB Output is correct
5 Correct 174 ms 85652 KB Output is correct
6 Execution timed out 2011 ms 95140 KB Time limit exceeded
7 Correct 19 ms 78932 KB Output is correct
8 Correct 16 ms 78940 KB Output is correct
9 Correct 27 ms 64380 KB Output is correct
10 Correct 12 ms 64348 KB Output is correct
11 Correct 14 ms 78940 KB Output is correct
12 Correct 13 ms 66560 KB Output is correct
13 Correct 551 ms 72304 KB Output is correct
14 Correct 265 ms 69588 KB Output is correct
15 Correct 35 ms 69464 KB Output is correct
16 Correct 520 ms 67304 KB Output is correct
17 Execution timed out 2021 ms 76828 KB Time limit exceeded
18 Correct 101 ms 76668 KB Output is correct
19 Correct 1511 ms 76616 KB Output is correct
20 Execution timed out 2037 ms 76148 KB Time limit exceeded
21 Execution timed out 2041 ms 85984 KB Time limit exceeded
22 Correct 189 ms 85648 KB Output is correct
23 Execution timed out 2055 ms 82956 KB Time limit exceeded
24 Correct 169 ms 85592 KB Output is correct
25 Correct 490 ms 94540 KB Output is correct
26 Correct 450 ms 90848 KB Output is correct
27 Correct 743 ms 94580 KB Output is correct
28 Execution timed out 2017 ms 95376 KB Time limit exceeded
29 Execution timed out 2021 ms 95048 KB Time limit exceeded
30 Execution timed out 2044 ms 95220 KB Time limit exceeded
31 Execution timed out 2047 ms 89840 KB Time limit exceeded
32 Execution timed out 2029 ms 95108 KB Time limit exceeded