Submission #1256273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256273		ericl23302	Tracks in the Snow (BOI13_tracks)	C++20	86.88 / 100	1943 ms	1114112 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

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

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

            if (i && grid[i - 1][j]) {
                if (grid[i - 1][j] == grid[i][j]) {
                    adjacency[i * w - w + j].emplace_back(i * w + j, 0);
                    adjacency[i * w + j].emplace_back(i * w - w + j, 0);
                } else {
                    adjacency[i * w - w + j].emplace_back(i * w + j, 1);
                    adjacency[i * w + j].emplace_back(i * w - w + j, 1);
                }
            }

            if (j && grid[i][j - 1]) {
                if (grid[i][j - 1] == grid[i][j]) {
                    adjacency[i * w - 1 + j].emplace_back(i * w + j, 0);
                    adjacency[i * w + j].emplace_back(i * w - 1 + j, 0);
                } else {
                    adjacency[i * w - 1 + j].emplace_back(i * w + j, 1);
                    adjacency[i * w + j].emplace_back(i * w - 1 + j, 1);
                }
            }
        }
    }

    vector<int> distances(h * w, -1);
    distances[0] = 1;
    deque<int> q;
    q.push_front(0);

    while (!q.empty()) {
        int cur = q.front();
        q.pop_front();

        for (auto &i : adjacency[cur]) {
            if (distances[i.first] != -1) continue;
            distances[i.first] = distances[cur] + i.second;
            if (i.second)
                q.push_back(i.first);
            else
                q.push_front(i.first);
        }
    }

    int res = 0;
    for (auto &i : distances) res = max(res, i);

    cout << res << '\n';

    return 0;
}

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