Submission #1120552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120552		Captain_Georgia	Tracks in the Snow (BOI13_tracks)	C++17	20.83 / 100	2093 ms	1048576 KiB

tracks

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

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, M;
    cin >> N >> M;
    vector<vector<int>> arr(N, vector<int>(M));
    map<char, int> val;
    val['.'] = 1;
    val['F'] = 2;
    val['R'] = 3;
    for (int i = 0;i < N;i ++) {
        for (int j = 0;j < M;j ++) {
            char c;
            cin >> c;
            arr[i][j] = val[c];
        }
    }
    assert (arr[0][0] == arr[N - 1][M - 1] && arr[0][0] > 1);
    
    vector<int> X = {0, 0, 1, -1};
    vector<int> Y = {1, -1, 0, 0};
    vector<vector<int>> used(N, vector<int>(M, 0)), submx(N, vector<int>(M, 0));
    map<array<int, 2>, vector<array<int, 2>>> g;
    auto check = [&](int x, int y) -> bool {
        if (x < 0 || x >= N || y < 0 || y >= M || used[x][y] == 1 || arr[x][y] <= 1) return 0;
        return 1;
    };
    function<void(int, int, int, int)> dfs_init = [&](int sx, int sy, int _x, int _y) -> void {
        used[sx][sy] = 1;
        for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) {
            if (arr[_x][_y] == arr[X[i] + sx][Y[i] + sy]) {
                dfs_init (X[i] + sx, Y[i] + sy, _x, _y);
            }
        }
        for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) {
            if (arr[_x][_y] != arr[X[i] + sx][Y[i] + sy]) {
                g[{_x, _y}].push_back({X[i] + sx, Y[i] + sy});
                dfs_init (X[i] + sx, Y[i] + sy, X[i] + sx, Y[i] + sy);
            }
        }
    };
    dfs_init (0, 0, 0, 0);

    function<void(int, int)> dfs = [&](int sx, int sy) -> void {
        // cout << sx << " " << sy << " -- ";
        // for (auto [vx, vy] : g[{sx, sy}]) {
        //     cout << vx << " " << vy << ", ";
        // } cout << "\n";
        for (auto [vx, vy] : g[{sx, sy}]) {
            dfs (vx, vy);
            submx[sx][sy] = max(submx[sx][sy], submx[vx][vy]);
        }
        submx[sx][sy] ++;
    };
    dfs (0, 0);

    cout << submx[0][0] << "\n";
}

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