oj.uz

Submission #881443

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

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;
        }
    }

    dist[0][0] = 1;
    q.push({0, 0});
    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});
                    }
                }
            }
        }
    }

    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 211 ms 9392 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 20 ms 9048 KB Output is correct
5 Correct 11 ms 6748 KB Output is correct
6 Correct 1 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 3 ms 4700 KB Output is correct
12 Correct 51 ms 7448 KB Output is correct
13 Correct 11 ms 6748 KB Output is correct
14 Correct 11 ms 6748 KB Output is correct
15 Correct 101 ms 9308 KB Output is correct
16 Correct 213 ms 9304 KB Output is correct
17 Correct 112 ms 9340 KB Output is correct
18 Correct 20 ms 9048 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 62044 KB Output is correct
2 Correct 566 ms 23804 KB Output is correct
3 Execution timed out 2033 ms 89400 KB Time limit exceeded
4 Correct 1476 ms 37968 KB Output is correct
5 Correct 119 ms 62500 KB Output is correct
6 Execution timed out 2067 ms 89948 KB Time limit exceeded
7 Correct 8 ms 62300 KB Output is correct
8 Correct 8 ms 62044 KB Output is correct
9 Correct 16 ms 2820 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 7 ms 62192 KB Output is correct
12 Correct 1 ms 4696 KB Output is correct
13 Correct 572 ms 24084 KB Output is correct
14 Correct 274 ms 16728 KB Output is correct
15 Correct 13 ms 18776 KB Output is correct
16 Correct 551 ms 10088 KB Output is correct
17 Execution timed out 2091 ms 40528 KB Time limit exceeded
18 Correct 57 ms 39800 KB Output is correct
19 Correct 1517 ms 37796 KB Output is correct
20 Execution timed out 2024 ms 35548 KB Time limit exceeded
21 Execution timed out 2007 ms 64564 KB Time limit exceeded
22 Correct 116 ms 62204 KB Output is correct
23 Execution timed out 2066 ms 55376 KB Time limit exceeded
24 Correct 102 ms 64340 KB Output is correct
25 Correct 373 ms 89392 KB Output is correct
26 Correct 433 ms 75812 KB Output is correct
27 Correct 689 ms 89412 KB Output is correct
28 Execution timed out 2040 ms 90220 KB Time limit exceeded
29 Execution timed out 2065 ms 90140 KB Time limit exceeded
30 Execution timed out 2079 ms 87928 KB Time limit exceeded
31 Execution timed out 2044 ms 68488 KB Time limit exceeded
32 Execution timed out 2009 ms 94060 KB Time limit exceeded