oj.uz

Submission #891814

# Submission time Handle Problem Language Result Execution time Memory
891814 2023-12-24T05:45:27 Z seriouslyFlawed Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1100 ms 119196 KB 
#include <bits/stdc++.h>

using namespace std;

// Shortcuts for common operations
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define ll long long
#define endl "\n"

// Type definitions for convenience
typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef unordered_set<int> usi;
typedef unordered_map<int, int> umii;

// Debugging macros
#define debug(x) cerr << #x << " = " << (x) << '\n'
#define debug_vector(v) _debug_vector(#v, v)
template<typename T>
void _debug_vector(const string& name, const vector<T>& a) {
    cerr << name << " = [ ";
    for(const auto &x : a) cerr << x << ' ';
    cerr << "]\n";
}

// I/O redirection for local testing
#define iofile(io) \
        freopen((io + ".in").c_str(), "r", stdin); \
        freopen((io + ".out").c_str(), "w", stdout);

// delta for floodfill
vi dx = {0, 1, 0, -1};
vi dy = {1, 0, -1, 0};

// extended deltas for floodfill
vi edx = {0, 1, 0, -1, 1, 1, -1, -1};
vi edy = {1, 0, -1, 0, 1, -1, 1, -1};

// Common outputs
void yes() { cout << "YES" << '\n'; }
void no() { cout << "NO" << '\n'; }

// cin.tie(0)->sync_with_stdio(0);

void fx() {
    // Functionality for fx
    int n, m;
    cin >> n >> m;

    vector<string>tab(n);
    for(auto &i: tab) cin >> i;

    vvi lvl(n, vi(m, 0));
    lvl[0][0] = 1;

    queue<pii>q;
    q.push({0, 0});

    queue<pii>que;
    int res = 1;

    while(!q.empty()){
        while(!q.empty()){
            auto curr = q.front(); q.pop();

            for(int i = 0; i < 4; i++){
                pii next = {curr.f+dx[i], curr.s+dy[i]};

                if(next.f >= 0 and next.f <= n-1 and next.s >= 0 and next.s <= m-1){
                    if(tab[next.f][next.s] == '.' or lvl[next.f][next.s] != 0) continue;
                    

                    if(tab[next.f][next.s] == tab[curr.f][curr.s]){ q.push(next); lvl[next.f][next.s] = res; }
                    else{ que.push(next); lvl[next.f][next.s] = res+1; }
                }
            }
        }

        if(q.empty()){
            res++;
            swap(q, que);
        }
    }


    cout << (res-1) << endl;

}

int main() {
    // Uncomment the following lines for file I/O
    // iofile(string("hello"));
    
    // Uncomment the following lines for multiple test cases
    // int t; cin >> t;
    // while(t--) fx();
    
    // Single test case
    fx();
    
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2140 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 7 ms 1372 KB Output is correct
5 Correct 3 ms 804 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 3 ms 840 KB Output is correct
15 Correct 11 ms 2196 KB Output is correct
16 Correct 12 ms 2140 KB Output is correct
17 Correct 9 ms 1884 KB Output is correct
18 Correct 6 ms 1352 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 66 ms 10532 KB Output is correct
3 Correct 362 ms 108868 KB Output is correct
4 Correct 102 ms 25996 KB Output is correct
5 Correct 216 ms 55892 KB Output is correct
6 Correct 1100 ms 119152 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 53 ms 10376 KB Output is correct
14 Correct 30 ms 6488 KB Output is correct
15 Correct 23 ms 7260 KB Output is correct
16 Correct 24 ms 4332 KB Output is correct
17 Correct 151 ms 27828 KB Output is correct
18 Correct 99 ms 27476 KB Output is correct
19 Correct 96 ms 26004 KB Output is correct
20 Correct 81 ms 23880 KB Output is correct
21 Correct 209 ms 57896 KB Output is correct
22 Correct 211 ms 55888 KB Output is correct
23 Correct 295 ms 47936 KB Output is correct
24 Correct 243 ms 56672 KB Output is correct
25 Correct 571 ms 108932 KB Output is correct
26 Correct 519 ms 73556 KB Output is correct
27 Correct 734 ms 110568 KB Output is correct
28 Correct 983 ms 119196 KB Output is correct
29 Correct 961 ms 117452 KB Output is correct
30 Correct 837 ms 114796 KB Output is correct
31 Correct 658 ms 63252 KB Output is correct
32 Correct 676 ms 110160 KB Output is correct