Submission #1120761

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

tracks

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

typedef long long ll;

struct DSU {
    vector<vector<array<int, 2>>> par;
    vector<vector<int>> sz;
    void init (int N, int M) {
        par.resize(N + 1);
        sz.resize(N + 1);
        for (int i = 0;i < N;i ++) {
            par[i].assign(M + 1, {-1, -1});
            sz[i].assign(M + 1, 1);
        }
    }
    array<int, 2> get_par (array<int, 2> x) {
        if (par[x[0]][x[1]][0] == -1) return x;
        return par[x[0]][x[1]] = get_par(par[x[0]][x[1]]);
    }
    void add (array<int, 2> a, array<int, 2> b) {
        a = get_par(a);
        b = get_par(b);
        if (a == b) return;
        if (sz[a[0]][a[1]] < sz[b[0]][b[1]]) swap (a, b);
        sz[a[0]][a[1]] += sz[b[0]][b[1]];
        par[b[0]][b[1]] = a;
    }    
};

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 ++) {
        string S;
        cin >> S;
        for (int j = 0;j < M;j ++) {
            arr[i][j] = val[S[j]];
        }
    }
    assert (arr[0][0] == arr[N - 1][M - 1] && arr[0][0] > 1);

    // for (int i = 0;i < N;i ++) {
    //     for (int j = 0;j < M;j ++) {
    //         cout << arr[i][j] << " ";
    //     } cout << "\n";
    // } cout << "\n";
    
    DSU DS;
    DS.init (N, M);
    vector<int> X = {1, -1, 0, 0};
    vector<int> Y = {0, 0, 1, -1};
    vector<vector<int>> used(N, vector<int>(M, 0)), submx(N, vector<int>(M, 0));
    map<array<int, 2>, set<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;
    };
    
    for (int i = 0;i < N;i ++) {
        for (int j = 0;j < M;j ++) {
            for (int t = 0;t < 4;t ++) if (check (i + X[t], j + Y[t])) {
                if (arr[i][j] == arr[i + X[t]][j + Y[t]]) {
                    DS.add ({i, j}, {i + X[t], j + Y[t]});
                }
            }
        }
    }

    for (int i = 0;i < N;i ++) for (int j = 0;j < M;j ++) used[i][j] = 0;
    function<void(int, int)> dfss = [&](int sx, int sy) -> void {
        used[sx][sy] = 1;
        for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) {
            if (arr[sx][sy] == arr[X[i] + sx][Y[i] + sy]) {
                dfss (X[i] + sx, Y[i] + sy);
            } else {
                if (DS.get_par ({sx, sy}) != DS.get_par ({X[i] + sx, Y[i] + sy})) {
                    if (g[DS.get_par ({sx, sy})].find(DS.get_par ({X[i] + sx, Y[i] + sy})) == g[DS.get_par ({sx, sy})].end() && g[DS.get_par ({X[i] + sx, Y[i] + sy})].find(DS.get_par ({sx, sy})) == g[DS.get_par ({sx + X[i], sy + Y[i]})].end()) {
                        g[DS.get_par ({sx, sy})].insert(DS.get_par ({X[i] + sx, Y[i] + sy}));
                    }
                }
                dfss (X[i] + sx, Y[i] + sy);
            }
        }
    };
    dfss (0, 0);
    // queue<array<int, 4>> q;
    // q.push({0, 0, 0, 0});
    // used[0][0] = 1;
    // while (q.size() > 0) {
    //     auto [sx, sy, _x, _y] = q.front();
    //     q.pop();
    //     for (int i = 0;i < 4;i ++) if (check (X[i] + sx, Y[i] + sy) == true) {
    //         if (arr[sx][sy] != arr[X[i] + sx][Y[i] + sy]) {
    //             used[X[i] + sx][Y[i] + sy] = 1;
    //             g[{_x, _y}].push_back({X[i] + sx, Y[i] + sy});
    //             q.push({X[i] + sx, Y[i] + sy, X[i] + sx, Y[i] + sy});
    //             // dfs_init (X[i] + sx, Y[i] + sy, X[i] + sx, Y[i] + sy);
    //         } else {

    //         }
    //     }
    // }

    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";
}
/*
5 6
RRRRRR
.R...R
FRRFRR
FR....
.RRRRR
*/

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