oj.uz

Submission #1065838

# Submission time Handle Problem Language Result Execution time Memory
1065838 2024-08-19T12:13:51 Z ortsac Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 1291 ms 220268 KB 
#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});
            }
        }
    }
    // calc componentes
    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++;
        }
    }
    // resposta
    if (mat[1][1] == 'F') {
        if (cF > cR) cout << cR + 2 << "\n";
        else cout << cF + 1 << "\n";
    } else {
        if (cR > cF) cout << cF + 2 << "\n";
        else cout << cR + 1 << "\n";
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 9304 KB Output isn't correct
2 Incorrect 1 ms 600 KB Output isn't correct
3 Incorrect 1 ms 860 KB Output isn't correct
4 Incorrect 14 ms 8296 KB Output isn't correct
5 Incorrect 6 ms 4556 KB Output isn't correct
6 Incorrect 1 ms 600 KB Output isn't correct
7 Incorrect 1 ms 856 KB Output isn't correct
8 Incorrect 1 ms 1112 KB Output isn't correct
9 Incorrect 1 ms 1628 KB Output isn't correct
10 Incorrect 6 ms 3676 KB Output isn't correct
11 Incorrect 4 ms 3164 KB Output isn't correct
12 Incorrect 8 ms 4964 KB Output isn't correct
13 Incorrect 6 ms 4700 KB Output isn't correct
14 Incorrect 5 ms 4700 KB Output isn't correct
15 Incorrect 18 ms 8860 KB Output isn't correct
16 Incorrect 21 ms 9304 KB Output isn't correct
17 Incorrect 21 ms 9052 KB Output isn't correct
18 Incorrect 15 ms 8284 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 46684 KB Output isn't correct
2 Incorrect 79 ms 26648 KB Output isn't correct
3 Incorrect 637 ms 132948 KB Output isn't correct
4 Incorrect 180 ms 67924 KB Output isn't correct
5 Incorrect 322 ms 104016 KB Output isn't correct
6 Incorrect 1236 ms 220240 KB Output isn't correct
7 Incorrect 26 ms 48728 KB Output isn't correct
8 Incorrect 21 ms 46684 KB Output isn't correct
9 Incorrect 3 ms 1116 KB Output isn't correct
10 Incorrect 2 ms 656 KB Output isn't correct
11 Incorrect 19 ms 47772 KB Output isn't correct
12 Incorrect 2 ms 2396 KB Output isn't correct
13 Incorrect 89 ms 26960 KB Output isn't correct
14 Incorrect 48 ms 18000 KB Output isn't correct
15 Incorrect 56 ms 24916 KB Output isn't correct
16 Incorrect 40 ms 10380 KB Output isn't correct
17 Incorrect 192 ms 52816 KB Output isn't correct
18 Incorrect 208 ms 75092 KB Output isn't correct
19 Incorrect 178 ms 67920 KB Output isn't correct
20 Incorrect 151 ms 45400 KB Output isn't correct
21 Incorrect 393 ms 94292 KB Output isn't correct
22 Incorrect 336 ms 103868 KB Output isn't correct
23 Incorrect 388 ms 83536 KB Output isn't correct
24 Incorrect 364 ms 90012 KB Output isn't correct
25 Incorrect 802 ms 220044 KB Output isn't correct
26 Incorrect 1032 ms 190924 KB Output isn't correct
27 Incorrect 1242 ms 220268 KB Output isn't correct
28 Incorrect 1291 ms 219984 KB Output isn't correct
29 Incorrect 1268 ms 220028 KB Output isn't correct
30 Incorrect 1248 ms 215716 KB Output isn't correct
31 Incorrect 865 ms 166224 KB Output isn't correct
32 Incorrect 1122 ms 220088 KB Output isn't correct