oj.uz

Submission #418005

# Submission time Handle Problem Language Result Execution time Memory
418005 2021-06-04T20:47:54 Z ilmar Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 827 ms 33948 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int h, w;
    cin >> h >> w;
    vector<vector<char>> grid(h, vector<char>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> grid[i][j];
        }
    }

    int ans = 0;
    bool done = false;
    char last = grid[0][0];
    queue<pair<int, int>> q;
    vector<vector<bool>> vis(h, vector<bool>(w, false));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (!vis[i][j] && grid[i][j] != '.') {
                q.push({i, j});
                vis[i][j] = true;
                if (grid[i][j] == last)
                    ans++;
                else if (!done) {
                    ans++;
                    done = true;
                }
            }
            while (!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                
                if (x + 1 < h && grid[x + 1][y] == grid[i][j] && !vis[x + 1][y]) {
                    vis[x + 1][y] = true;
                    q.push({x + 1, y});
                }
                if (x - 1 >= 0 && grid[x - 1][y] == grid[i][j] && !vis[x - 1][y]) {
                    vis[x - 1][y] = true;                
                    q.push({x - 1, y});
                }

                if (y + 1 < w && grid[x][y + 1] == grid[i][j] && !vis[x][y + 1]) {
                    vis[x][y + 1] = true;
                    q.push({x, y + 1});
                }
                if (y - 1 >= 0 && grid[x][y - 1] == grid[i][j] && !vis[x][y - 1]) {
                    vis[x][y - 1] = true;
                    q.push({x, y - 1});
                }
            }
        }
    }

    cout << ans << endl;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 808 KB Output isn't correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Incorrect 8 ms 588 KB Output isn't correct
5 Incorrect 3 ms 460 KB Output isn't correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 4 ms 460 KB Output isn't correct
11 Incorrect 2 ms 332 KB Output isn't correct
12 Incorrect 6 ms 460 KB Output isn't correct
13 Incorrect 3 ms 460 KB Output isn't correct
14 Incorrect 3 ms 460 KB Output isn't correct
15 Incorrect 13 ms 824 KB Output isn't correct
16 Incorrect 15 ms 864 KB Output isn't correct
17 Incorrect 10 ms 844 KB Output isn't correct
18 Incorrect 9 ms 672 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 844 KB Output isn't correct
2 Incorrect 54 ms 3660 KB Output isn't correct
3 Incorrect 421 ms 33916 KB Output isn't correct
4 Incorrect 98 ms 8228 KB Output isn't correct
5 Incorrect 253 ms 19164 KB Output isn't correct
6 Incorrect 811 ms 33920 KB Output isn't correct
7 Incorrect 3 ms 832 KB Output isn't correct
8 Incorrect 3 ms 844 KB Output isn't correct
9 Incorrect 3 ms 328 KB Output isn't correct
10 Incorrect 1 ms 380 KB Output isn't correct
11 Incorrect 3 ms 824 KB Output isn't correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Incorrect 55 ms 3644 KB Output isn't correct
14 Incorrect 32 ms 2244 KB Output isn't correct
15 Incorrect 35 ms 2448 KB Output isn't correct
16 Incorrect 27 ms 1740 KB Output isn't correct
17 Incorrect 139 ms 8812 KB Output isn't correct
18 Incorrect 121 ms 8804 KB Output isn't correct
19 Incorrect 106 ms 8232 KB Output isn't correct
20 Incorrect 96 ms 7604 KB Output isn't correct
21 Incorrect 254 ms 19924 KB Output isn't correct
22 Incorrect 264 ms 19176 KB Output isn't correct
23 Incorrect 263 ms 16560 KB Output isn't correct
24 Incorrect 254 ms 19408 KB Output isn't correct
25 Incorrect 482 ms 33916 KB Output isn't correct
26 Correct 557 ms 26112 KB Output is correct
27 Incorrect 711 ms 33948 KB Output isn't correct
28 Incorrect 794 ms 33920 KB Output isn't correct
29 Incorrect 827 ms 33924 KB Output isn't correct
30 Incorrect 777 ms 33228 KB Output isn't correct
31 Incorrect 630 ms 21892 KB Output isn't correct
32 Incorrect 651 ms 33860 KB Output isn't correct