Submission #1311506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311506		madamadam3	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1768 ms	130992 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
#define Q (t%2==1 ? q1 : q2)
#define G (t%2==0 ? q1 : q2)

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int h, w; cin >> h >> w;
    vector<vector<int>> grid(h, vector<int>(w, 0));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char x; cin >> x;
            if (x == 'R') grid[i][j] = 1;
            else if (x == 'F') grid[i][j] = 2;
        }
    }

    auto coord = [&](int x, int y) {
        return w*x + y;
    };

    auto pc = [&](int c) {
        return make_pair(c/w, c%w);
    };

    auto adj = [&](int c) {
        vector<int> r;
        auto k = pc(c);
        for (int dx = k.first-1; dx <= k.first+1; dx++) {
            for (int dy = k.second-1; dy <= k.second+1; dy++) {
                if (dx == k.first && dy == k.second) continue;
                if (dx != k.first && dy != k.second) continue;
                if (dx < 0 || dx >= h || dy < 0 || dy >= w) continue;
                r.push_back(coord(dx, dy));
            }
        }
        return r;
    };

    int t = 0, p = grid[0][0];
    vector<int> seen(h*w, 0);
    queue<int> q1, q2; q1.push(0); seen[0]++;

    while (!(q1.empty() && q2.empty())) {
        t++;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (auto v : adj(u)) {
                if (seen[v]) continue;
                int typ = grid[pc(v).first][pc(v).second];

                if (typ == 0) continue;
                else if (typ == p) Q.push(v);
                else G.push(v);

                seen[v]++;
            }
        }

        p = 3 - p;
    }

    cout << t << "\n";
    return 0;
}

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