oj.uz

Submission #594556

# Submission time Handle Problem Language Result Execution time Memory
594556 2022-07-12T16:43:57 Z bogdanvladmihai Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 1158 ms 47468 KB 
#include <bits/stdc++.h>
using namespace std;

/***
Last animal to enter the maze is in mat[0][0]

***/

const int MAXN = 4000;
const int ox[] = {0, 1, 0, -1};
const int oy[] = {1, 0, -1, 0};

int n, m;
char mat[MAXN + 1][MAXN + 1];
bool used[MAXN + 1][MAXN + 1];

bool inside(const int x, const int y) {
    if (x >= 0 && y >= 0 && x < n && y < m) {
        return true;
    }

    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
        }
    }

    const char target = mat[0][0];

    queue<pair<int, int>> q;
    int ans = 0, add = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!used[i][j] && mat[i][j] == target) {
                ans++;
                q.push(make_pair(i, j));
                while (!q.empty()) {
                    int x, y;
                    tie(x, y) = q.front();
                    q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = x + ox[k];
                        int ny = y + oy[k];

                        if (inside(nx, ny) && !used[nx][ny] && mat[nx][ny] == target) {
                            used[nx][ny] = true;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
            } else if (mat[i][j] != target) {
                add = 1;
            }
        }
    }

    cout << ans + add << "\n";

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 4308 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Incorrect 1 ms 700 KB Output isn't correct
4 Incorrect 13 ms 4308 KB Output isn't correct
5 Incorrect 7 ms 2584 KB Output isn't correct
6 Incorrect 1 ms 436 KB Output isn't correct
7 Incorrect 1 ms 596 KB Output isn't correct
8 Incorrect 1 ms 724 KB Output isn't correct
9 Incorrect 1 ms 1088 KB Output isn't correct
10 Incorrect 6 ms 2260 KB Output isn't correct
11 Incorrect 4 ms 1876 KB Output isn't correct
12 Incorrect 9 ms 2612 KB Output isn't correct
13 Incorrect 7 ms 2628 KB Output isn't correct
14 Incorrect 8 ms 2644 KB Output isn't correct
15 Incorrect 20 ms 4388 KB Output isn't correct
16 Incorrect 20 ms 4272 KB Output isn't correct
17 Incorrect 18 ms 4288 KB Output isn't correct
18 Incorrect 13 ms 4308 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 30192 KB Output isn't correct
2 Incorrect 111 ms 11540 KB Output isn't correct
3 Incorrect 950 ms 47244 KB Output isn't correct
4 Incorrect 222 ms 18648 KB Output isn't correct
5 Incorrect 533 ms 32568 KB Output isn't correct
6 Incorrect 1137 ms 47468 KB Output isn't correct
7 Incorrect 18 ms 31656 KB Output isn't correct
8 Incorrect 19 ms 30196 KB Output isn't correct
9 Incorrect 4 ms 468 KB Output isn't correct
10 Incorrect 2 ms 340 KB Output isn't correct
11 Incorrect 18 ms 31044 KB Output isn't correct
12 Incorrect 2 ms 1492 KB Output isn't correct
13 Incorrect 115 ms 11536 KB Output isn't correct
14 Incorrect 62 ms 8268 KB Output isn't correct
15 Incorrect 64 ms 9096 KB Output isn't correct
16 Incorrect 45 ms 3988 KB Output isn't correct
17 Incorrect 262 ms 20256 KB Output isn't correct
18 Incorrect 246 ms 19912 KB Output isn't correct
19 Incorrect 220 ms 18592 KB Output isn't correct
20 Incorrect 217 ms 17340 KB Output isn't correct
21 Incorrect 561 ms 33684 KB Output isn't correct
22 Incorrect 537 ms 32480 KB Output isn't correct
23 Incorrect 508 ms 27440 KB Output isn't correct
24 Incorrect 559 ms 33644 KB Output isn't correct
25 Incorrect 981 ms 47360 KB Output isn't correct
26 Correct 993 ms 39724 KB Output is correct
27 Incorrect 1142 ms 47328 KB Output isn't correct
28 Incorrect 1137 ms 47396 KB Output isn't correct
29 Incorrect 1158 ms 47360 KB Output isn't correct
30 Incorrect 1041 ms 46400 KB Output isn't correct
31 Incorrect 815 ms 35400 KB Output isn't correct
32 Incorrect 888 ms 47252 KB Output isn't correct