oj.uz

Submission #881435

# Submission time Handle Problem Language Result Execution time Memory
881435 2023-12-01T08:48:34 Z noompty Tracks in the Snow (BOI13_tracks) C++17
75.9375 / 100
 2000 ms 79956 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;

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 (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++) {
        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 223 ms 66632 KB Output is correct
2 Correct 12 ms 64344 KB Output is correct
3 Correct 14 ms 66536 KB Output is correct
4 Correct 32 ms 66600 KB Output is correct
5 Correct 23 ms 66392 KB Output is correct
6 Correct 12 ms 64376 KB Output is correct
7 Correct 13 ms 66536 KB Output is correct
8 Correct 13 ms 66396 KB Output is correct
9 Correct 13 ms 66396 KB Output is correct
10 Correct 18 ms 66492 KB Output is correct
11 Correct 16 ms 66524 KB Output is correct
12 Correct 59 ms 66396 KB Output is correct
13 Correct 23 ms 66392 KB Output is correct
14 Correct 23 ms 66396 KB Output is correct
15 Correct 109 ms 66628 KB Output is correct
16 Correct 221 ms 66704 KB Output is correct
17 Correct 122 ms 66640 KB Output is correct
18 Correct 31 ms 66392 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 78800 KB Output is correct
2 Correct 556 ms 70776 KB Output is correct
3 Execution timed out 2048 ms 79140 KB Time limit exceeded
4 Correct 1488 ms 73044 KB Output is correct
5 Correct 176 ms 76856 KB Output is correct
6 Execution timed out 2050 ms 79700 KB Time limit exceeded
7 Correct 15 ms 78684 KB Output is correct
8 Correct 15 ms 78684 KB Output is correct
9 Correct 28 ms 64456 KB Output is correct
10 Correct 13 ms 64420 KB Output is correct
11 Correct 15 ms 78684 KB Output is correct
12 Correct 14 ms 66396 KB Output is correct
13 Correct 554 ms 70780 KB Output is correct
14 Correct 273 ms 68692 KB Output is correct
15 Correct 32 ms 68432 KB Output is correct
16 Correct 529 ms 66652 KB Output is correct
17 Execution timed out 2004 ms 73352 KB Time limit exceeded
18 Correct 97 ms 72752 KB Output is correct
19 Correct 1419 ms 73336 KB Output is correct
20 Execution timed out 2056 ms 72780 KB Time limit exceeded
21 Execution timed out 2021 ms 76668 KB Time limit exceeded
22 Correct 173 ms 76880 KB Output is correct
23 Execution timed out 2050 ms 75332 KB Time limit exceeded
24 Correct 167 ms 76624 KB Output is correct
25 Correct 457 ms 78976 KB Output is correct
26 Correct 494 ms 78728 KB Output is correct
27 Correct 681 ms 78932 KB Output is correct
28 Execution timed out 2055 ms 79836 KB Time limit exceeded
29 Execution timed out 2049 ms 79600 KB Time limit exceeded
30 Execution timed out 2033 ms 79496 KB Time limit exceeded
31 Execution timed out 2052 ms 79956 KB Time limit exceeded
32 Execution timed out 2078 ms 79216 KB Time limit exceeded