Submission #1065802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065802		ortsac	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	1298 ms	220532 KiB

tracks

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

#define pii pair<int, int>
#define fr first
#define se second

const int MAXT = 4e3 + 10;
char mat[MAXT][MAXT];
pii dad[MAXT][MAXT];
int tam[MAXT][MAXT];
int cR = 0, cF = 0;

int n, m;
int x[] = {-1, 0, 0, 1};
int y[] = {0, -1, 1, 0};

bool valid(int i, int j) {
    return ((1 <= i) && (n >= i) && (j >= 1) && (j <= m));
}

pii find(pii x) {
    if (dad[x.fr][x.se] == x) return x;
    return dad[x.fr][x.se] = find(dad[x.fr][x.se]);
}

void print(pii a) {
    cout << a.fr << " " << a.se << "\n";
}

void join(pii a, pii b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (tam[a.fr][a.se] > tam[b.fr][b.se]) swap(a, b);
    tam[b.fr][b.se] += tam[a.fr][a.se];
    dad[a.fr][a.se] = b;
}

int32_t main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mat[i][j];
            if (mat[i][j] != '.') {
                tam[i][j] = 1;
                dad[i][j] = {i, j};
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mat[i][j] == '.') continue;
            for (int k = 0; k < 4; k++) {
                int a = i + x[k], b = j + y[k];
                if ((!valid(a, b)) || (mat[i][j] != mat[a][b])) continue;
                join({i, j}, {a, b});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mat[i][j] == '.') continue;
            if (dad[i][j] != make_pair(i, j)) continue;
            if (mat[i][j] == 'R') cR++;
            else cF++;
        }
    }
    cout << min(cR, cF) + 1 << "\n";
}

• Subtask 1: 0 / 30
• Subtask 2: 2.1875 / 70