Submission #1256297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256297		ericl23302	Tracks in the Snow (BOI13_tracks)	C++20	67.19 / 100	2129 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<char>> grid(h, vector<char>(w, 0));
    vector<vector<pair<int, bool>>> adjacency(h * w);
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];

            if (grid[i][j] == '.') 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);
                }
            }
        }
    }

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (adjacency[i * w + j].size() > 4) {
              cout << "ERROR!!!" << endl;
              return 0;
            }
        }
    }

    vector<short> 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, (int)i);

    cout << res << '\n';

    return 0;
}

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