제출 #1120845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120845		vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	1168 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;
    queue<array<int, 2>> q;
    int typ;
    function<void(int, int)> dfs_init = [&](int sx, int sy) -> void {
        used[sx][sy] = 1;
        for(int i = 0 ; i < 4;i++){
            int tx = X[i] + sx, ty = Y[i] + sy;
            if (check (tx, ty) == true) {
                if (arr[tx][ty] == typ) {
                    dfs_init (tx, ty);
                } else {
                    q.push({tx, ty});
                }
            }
        }
    };
    q.push({0, 0});
    int ans = 0;
    while (q.size() > 0) {
        auto [sx, sy] = q.front();
        q.pop();
        if (used[sx][sy] == 1) continue;
        // used[sx][sy] = 1;
        if (typ != arr[sx][sy]) ans ++;
        typ = arr[sx][sy];
        dfs_init (sx, sy);
    }
    cout << ans << "\n";
}
/*
5 6
RRRRRR
.R...R
FRRFRR
FR....
.RRRRR
*/

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