Submission #748300

#	Time	Username	Problem	Language	Result	Execution time	Memory
748300		54skyxenon	Tracks in the Snow (BOI13_tracks)	C++17	27.40 / 100	2103 ms	667724 KiB

tracks

// https://oj.uz/problem/view/BOI13_tracks

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define maxHW 4000

bool seen[maxHW][maxHW];
string grid[maxHW];

char invert(char c) {
    return (c == 'R') ? 'F' : 'R';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int h, w;
    cin >> h >> w;

    int tracks = 0;
    for (int i = 0; i < h; i++) {
        cin >> grid[i];
        for (int j = 0; j < w; j++) {
            tracks += (grid[i][j] != '.');
        }
    }

    set<pii> waiting({mp(0, 0)});
    char waiting_color = grid[0][0];

    int ans = 0;
    int num_seen = 0;

    while (num_seen < tracks) {
        ans++;

        queue<pii> Q;
        for (auto [r, c] : waiting) {
            Q.push(mp(r, c));
        }
        
        waiting.clear();

        while (!Q.empty()) {
            auto [r, c] = Q.front(); Q.pop();
            num_seen++;
            seen[r][c] = true;

            for (auto [nr, nc] : {mp(r + 1, c), mp(r - 1, c), mp(r, c + 1), mp(r, c - 1)}) {
                if (0 <= nr && nr < h && 0 <= nc && nc < w && !seen[nr][nc]) {
                    if (grid[nr][nc] == waiting_color) {
                        Q.push(mp(nr, nc));
                    }
                    else if (grid[nr][nc] == invert(waiting_color)) {
                        waiting.insert(mp(nr, nc));
                    }
                }
            }
        }

        waiting_color = invert(waiting_color);
    }

    cout << ans << '\n';
}

• Subtask 1: 3.3333333333333335 / 30
• Subtask 2: 24.0625 / 70