oj.uz

Submission #881431

# Submission time Handle Problem Language Result Execution time Memory
881431 2023-12-01T08:47:11 Z noompty Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
 2000 ms 79904 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 || 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_back({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 206 ms 66788 KB Output is correct
2 Correct 15 ms 64356 KB Output is correct
3 Correct 14 ms 66532 KB Output is correct
4 Correct 30 ms 66392 KB Output is correct
5 Correct 23 ms 66392 KB Output is correct
6 Correct 12 ms 64348 KB Output is correct
7 Correct 12 ms 66396 KB Output is correct
8 Correct 12 ms 66456 KB Output is correct
9 Correct 13 ms 66396 KB Output is correct
10 Correct 18 ms 66520 KB Output is correct
11 Correct 18 ms 66396 KB Output is correct
12 Correct 56 ms 66628 KB Output is correct
13 Correct 22 ms 66396 KB Output is correct
14 Correct 22 ms 66392 KB Output is correct
15 Correct 105 ms 66636 KB Output is correct
16 Correct 206 ms 66704 KB Output is correct
17 Correct 120 ms 66904 KB Output is correct
18 Correct 31 ms 66392 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 78684 KB Output is correct
2 Correct 575 ms 70780 KB Output is correct
3 Execution timed out 2025 ms 79172 KB Time limit exceeded
4 Correct 1410 ms 73060 KB Output is correct
5 Correct 188 ms 76852 KB Output is correct
6 Execution timed out 2035 ms 79400 KB Time limit exceeded
7 Correct 14 ms 78680 KB Output is correct
8 Correct 15 ms 78772 KB Output is correct
9 Correct 27 ms 64448 KB Output is correct
10 Correct 12 ms 64348 KB Output is correct
11 Correct 15 ms 78684 KB Output is correct
12 Correct 14 ms 66484 KB Output is correct
13 Correct 556 ms 71012 KB Output is correct
14 Correct 267 ms 68684 KB Output is correct
15 Correct 32 ms 68484 KB Output is correct
16 Correct 513 ms 66540 KB Output is correct
17 Correct 1945 ms 73080 KB Output is correct
18 Correct 96 ms 72752 KB Output is correct
19 Correct 1417 ms 73028 KB Output is correct
20 Execution timed out 2044 ms 72784 KB Time limit exceeded
21 Execution timed out 2069 ms 76884 KB Time limit exceeded
22 Correct 180 ms 76856 KB Output is correct
23 Execution timed out 2060 ms 75312 KB Time limit exceeded
24 Correct 159 ms 76624 KB Output is correct
25 Correct 470 ms 78672 KB Output is correct
26 Correct 448 ms 78940 KB Output is correct
27 Correct 639 ms 78972 KB Output is correct
28 Execution timed out 2040 ms 79232 KB Time limit exceeded
29 Execution timed out 2054 ms 79180 KB Time limit exceeded
30 Execution timed out 2039 ms 79424 KB Time limit exceeded
31 Execution timed out 2025 ms 79904 KB Time limit exceeded
32 Execution timed out 2065 ms 79220 KB Time limit exceeded