Submission #748298

#	Time	Username	Problem	Language	Result	Execution time	Memory
748298		54skyxenon	Tracks in the Snow (BOI13_tracks)	C++17	32.40 / 100	2106 ms	198468 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

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;
    vector<string> grid(h);
    for (int i = 0; i < h; i++) {
        cin >> grid[i];
        for (int j = 0; j < w; j++) {
            tracks += (grid[i][j] != '.');
        }
    }

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

    int ans = 0;
    while (seen.size() < 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();
            seen.insert(mp(r, c));

            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.count(mp(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';
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:34:24: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     while (seen.size() < tracks) {
      |            ~~~~~~~~~~~~^~~~~~~~

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