oj.uz

Submission #1065817

# Submission time Handle Problem Language Result Execution time Memory
1065817 2024-08-19T12:00:43 Z ortsac Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 1286 ms 204412 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 (min(cR, cF) == 0) cout << "1\n";
    else cout << "2\n";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 9052 KB Output isn't correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Incorrect 0 ms 860 KB Output isn't correct
4 Incorrect 14 ms 8144 KB Output isn't correct
5 Incorrect 5 ms 4444 KB Output isn't correct
6 Incorrect 0 ms 604 KB Output isn't correct
7 Incorrect 0 ms 860 KB Output isn't correct
8 Incorrect 1 ms 1116 KB Output isn't correct
9 Incorrect 1 ms 1628 KB Output isn't correct
10 Incorrect 4 ms 3676 KB Output isn't correct
11 Incorrect 4 ms 3164 KB Output isn't correct
12 Incorrect 9 ms 4936 KB Output isn't correct
13 Incorrect 5 ms 4444 KB Output isn't correct
14 Incorrect 5 ms 4620 KB Output isn't correct
15 Incorrect 17 ms 8728 KB Output isn't correct
16 Incorrect 22 ms 9052 KB Output isn't correct
17 Incorrect 17 ms 8792 KB Output isn't correct
18 Incorrect 15 ms 8028 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 46700 KB Output isn't correct
2 Incorrect 74 ms 25172 KB Output isn't correct
3 Incorrect 662 ms 117432 KB Output isn't correct
4 Incorrect 160 ms 64288 KB Output isn't correct
5 Incorrect 319 ms 95060 KB Output isn't correct
6 Incorrect 1219 ms 204220 KB Output isn't correct
7 Incorrect 17 ms 48716 KB Output isn't correct
8 Incorrect 16 ms 46680 KB Output isn't correct
9 Incorrect 3 ms 856 KB Output isn't correct
10 Incorrect 2 ms 604 KB Output isn't correct
11 Incorrect 18 ms 47680 KB Output isn't correct
12 Incorrect 2 ms 2396 KB Output isn't correct
13 Incorrect 83 ms 25576 KB Output isn't correct
14 Incorrect 44 ms 17244 KB Output isn't correct
15 Incorrect 56 ms 23896 KB Output isn't correct
16 Incorrect 34 ms 9816 KB Output isn't correct
17 Incorrect 185 ms 48976 KB Output isn't correct
18 Incorrect 209 ms 71096 KB Output isn't correct
19 Incorrect 160 ms 64180 KB Output isn't correct
20 Incorrect 135 ms 42076 KB Output isn't correct
21 Incorrect 364 ms 85220 KB Output isn't correct
22 Incorrect 310 ms 94876 KB Output isn't correct
23 Incorrect 380 ms 75836 KB Output isn't correct
24 Incorrect 377 ms 81192 KB Output isn't correct
25 Incorrect 776 ms 204188 KB Output isn't correct
26 Correct 961 ms 178772 KB Output is correct
27 Incorrect 1242 ms 204288 KB Output isn't correct
28 Incorrect 1250 ms 204368 KB Output isn't correct
29 Incorrect 1286 ms 204412 KB Output isn't correct
30 Incorrect 1190 ms 200340 KB Output isn't correct
31 Incorrect 815 ms 156240 KB Output isn't correct
32 Incorrect 1172 ms 204368 KB Output isn't correct