oj.uz

Submission #594558

# Submission time Handle Problem Language Result Execution time Memory
594558 2022-07-12T16:45:50 Z bogdanvladmihai Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 1199 ms 32244 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 << 1 + (ans >= 2) + add << "\n";

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 4316 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Incorrect 1 ms 596 KB Output isn't correct
4 Incorrect 14 ms 4308 KB Output isn't correct
5 Incorrect 7 ms 2540 KB Output isn't correct
6 Incorrect 1 ms 444 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 2 ms 1108 KB Output isn't correct
10 Incorrect 6 ms 2260 KB Output isn't correct
11 Incorrect 5 ms 1876 KB Output isn't correct
12 Incorrect 10 ms 2644 KB Output isn't correct
13 Incorrect 7 ms 2644 KB Output isn't correct
14 Incorrect 7 ms 2628 KB Output isn't correct
15 Incorrect 21 ms 4364 KB Output isn't correct
16 Incorrect 23 ms 4308 KB Output isn't correct
17 Incorrect 18 ms 4224 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 19 ms 30164 KB Output isn't correct
2 Incorrect 113 ms 10508 KB Output isn't correct
3 Incorrect 1002 ms 32064 KB Output isn't correct
4 Incorrect 242 ms 15456 KB Output isn't correct
5 Incorrect 575 ms 24100 KB Output isn't correct
6 Incorrect 1196 ms 31972 KB Output isn't correct
7 Incorrect 20 ms 31552 KB Output isn't correct
8 Incorrect 23 ms 30144 KB Output isn't correct
9 Incorrect 5 ms 452 KB Output isn't correct
10 Incorrect 3 ms 340 KB Output isn't correct
11 Incorrect 23 ms 30976 KB Output isn't correct
12 Incorrect 3 ms 1472 KB Output isn't correct
13 Incorrect 104 ms 10492 KB Output isn't correct
14 Incorrect 62 ms 7936 KB Output isn't correct
15 Incorrect 68 ms 8580 KB Output isn't correct
16 Incorrect 47 ms 3920 KB Output isn't correct
17 Incorrect 277 ms 16568 KB Output isn't correct
18 Incorrect 248 ms 16408 KB Output isn't correct
19 Incorrect 242 ms 15468 KB Output isn't correct
20 Incorrect 216 ms 14632 KB Output isn't correct
21 Incorrect 582 ms 24896 KB Output isn't correct
22 Incorrect 548 ms 24084 KB Output isn't correct
23 Incorrect 528 ms 20352 KB Output isn't correct
24 Incorrect 577 ms 25084 KB Output isn't correct
25 Incorrect 1010 ms 31996 KB Output isn't correct
26 Correct 1042 ms 28156 KB Output is correct
27 Incorrect 1199 ms 32244 KB Output isn't correct
28 Incorrect 1179 ms 32008 KB Output isn't correct
29 Incorrect 1169 ms 32200 KB Output isn't correct
30 Incorrect 1065 ms 31556 KB Output isn't correct
31 Incorrect 829 ms 25892 KB Output isn't correct
32 Incorrect 908 ms 31996 KB Output isn't correct