oj.uz

Submission #881428

# Submission time Handle Problem Language Result Execution time Memory
881428 2023-12-01T08:45:42 Z noompty Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
 2000 ms 92008 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 || 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 209 ms 66868 KB Output is correct
2 Correct 12 ms 64348 KB Output is correct
3 Correct 13 ms 66480 KB Output is correct
4 Correct 30 ms 66652 KB Output is correct
5 Correct 22 ms 66652 KB Output is correct
6 Correct 12 ms 64432 KB Output is correct
7 Correct 17 ms 66396 KB Output is correct
8 Correct 13 ms 66568 KB Output is correct
9 Correct 12 ms 66548 KB Output is correct
10 Correct 18 ms 66652 KB Output is correct
11 Correct 15 ms 66544 KB Output is correct
12 Correct 57 ms 66608 KB Output is correct
13 Correct 23 ms 66652 KB Output is correct
14 Correct 23 ms 66592 KB Output is correct
15 Correct 106 ms 66896 KB Output is correct
16 Correct 203 ms 66900 KB Output is correct
17 Correct 117 ms 66644 KB Output is correct
18 Correct 30 ms 66652 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 79040 KB Output is correct
2 Correct 544 ms 72236 KB Output is correct
3 Execution timed out 2092 ms 91200 KB Time limit exceeded
4 Correct 1400 ms 76148 KB Output is correct
5 Correct 173 ms 83540 KB Output is correct
6 Execution timed out 2016 ms 92008 KB Time limit exceeded
7 Correct 14 ms 78940 KB Output is correct
8 Correct 15 ms 78928 KB Output is correct
9 Correct 26 ms 64344 KB Output is correct
10 Correct 12 ms 64348 KB Output is correct
11 Correct 15 ms 78928 KB Output is correct
12 Correct 13 ms 66652 KB Output is correct
13 Correct 543 ms 72308 KB Output is correct
14 Correct 264 ms 69456 KB Output is correct
15 Correct 31 ms 69460 KB Output is correct
16 Correct 505 ms 67540 KB Output is correct
17 Correct 1967 ms 75648 KB Output is correct
18 Correct 90 ms 74832 KB Output is correct
19 Correct 1379 ms 75320 KB Output is correct
20 Execution timed out 2059 ms 74828 KB Time limit exceeded
21 Execution timed out 2013 ms 81752 KB Time limit exceeded
22 Correct 172 ms 81268 KB Output is correct
23 Execution timed out 2037 ms 79336 KB Time limit exceeded
24 Correct 221 ms 81272 KB Output is correct
25 Correct 467 ms 86864 KB Output is correct
26 Correct 466 ms 85080 KB Output is correct
27 Correct 634 ms 87140 KB Output is correct
28 Execution timed out 2090 ms 87556 KB Time limit exceeded
29 Execution timed out 2036 ms 87876 KB Time limit exceeded
30 Execution timed out 2056 ms 87388 KB Time limit exceeded
31 Execution timed out 2055 ms 84880 KB Time limit exceeded
32 Execution timed out 2009 ms 87524 KB Time limit exceeded