oj.uz

Submission #881439

# Submission time Handle Problem Language Result Execution time Memory
881439 2023-12-01T08:51:58 Z noompty Tracks in the Snow (BOI13_tracks) C++17
75.9375 / 100
 2000 ms 81748 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;
string grid[4005];
queue<pair<int, int>> q;

void bfs(int sr, int sc) {
    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 (nr >= 0 && nr < h && nc >= 0 && nc < w && grid[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++) {
        cin >> grid[i];
        for (int j = 0; j < w; j++) {
            dist[i][j] = 2e9;
        }
    }

    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 218 ms 9300 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 21 ms 8792 KB Output is correct
5 Correct 11 ms 6744 KB Output is correct
6 Correct 0 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 6 ms 4700 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Correct 50 ms 6888 KB Output is correct
13 Correct 11 ms 6748 KB Output is correct
14 Correct 11 ms 6852 KB Output is correct
15 Correct 102 ms 9096 KB Output is correct
16 Correct 214 ms 9048 KB Output is correct
17 Correct 119 ms 9052 KB Output is correct
18 Correct 20 ms 8792 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 62044 KB Output is correct
2 Correct 572 ms 22828 KB Output is correct
3 Execution timed out 2019 ms 81232 KB Time limit exceeded
4 Correct 1499 ms 35512 KB Output is correct
5 Correct 111 ms 57536 KB Output is correct
6 Execution timed out 2068 ms 81560 KB Time limit exceeded
7 Correct 8 ms 62296 KB Output is correct
8 Correct 7 ms 62152 KB Output is correct
9 Correct 16 ms 2648 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Correct 8 ms 62124 KB Output is correct
12 Correct 1 ms 4856 KB Output is correct
13 Correct 618 ms 22624 KB Output is correct
14 Correct 275 ms 15964 KB Output is correct
15 Correct 13 ms 18008 KB Output is correct
16 Correct 548 ms 9580 KB Output is correct
17 Execution timed out 2021 ms 37904 KB Time limit exceeded
18 Correct 58 ms 37464 KB Output is correct
19 Correct 1493 ms 35604 KB Output is correct
20 Execution timed out 2033 ms 33124 KB Time limit exceeded
21 Execution timed out 2040 ms 59924 KB Time limit exceeded
22 Correct 126 ms 57540 KB Output is correct
23 Execution timed out 2080 ms 50652 KB Time limit exceeded
24 Correct 98 ms 59484 KB Output is correct
25 Correct 370 ms 80944 KB Output is correct
26 Correct 467 ms 69676 KB Output is correct
27 Correct 643 ms 80724 KB Output is correct
28 Execution timed out 2067 ms 81512 KB Time limit exceeded
29 Execution timed out 2029 ms 81748 KB Time limit exceeded
30 Execution timed out 2024 ms 80112 KB Time limit exceeded
31 Execution timed out 2005 ms 63664 KB Time limit exceeded
32 Execution timed out 2039 ms 81424 KB Time limit exceeded