oj.uz

Submission #811974

# Submission time Handle Problem Language Result Execution time Memory
811974 2023-08-07T06:39:20 Z devariaota Tracks in the Snow (BOI13_tracks) C++17
50.5208 / 100
 756 ms 51872 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 4e3 + 5;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

queue<pair<int, int>> q1, q2;
char a[N][N];
bool vis[N][N];

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int h, w, cnt = 0, ans = 0;
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
            if (a[i][j] != '.') cnt++;
        }
    }
    q1.push({1, 1});
    vis[1][1] = 1, cnt--;
    while (cnt > 0) {
        ans++;
        while (!q1.empty()) {
            int x = q1.front().fi, y = q1.front().se;
            q1.pop();
            cnt--;
            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i], ty = y + dy[i];
                if (tx < 1 or ty < 1 or tx > h or ty > w or vis[tx][ty] or a[tx][ty] == '.') continue;
                else if (a[x][y] == a[tx][ty]) vis[tx][ty] = 1, q1.push({tx, ty});
                else vis[tx][ty] = 1, q2.push({tx, ty});
            }
        }
        q1 = q2;
        while (!q2.empty()) q2.pop();
    }
    cout << ans << "\n";
}

Subtask #1
13.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 4180 KB Output isn't correct
2 Incorrect 0 ms 468 KB Output isn't correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 7 ms 4436 KB Output is correct
5 Incorrect 4 ms 2516 KB Output isn't correct
6 Incorrect 0 ms 468 KB Output isn't correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Incorrect 1 ms 1108 KB Output isn't correct
10 Correct 3 ms 2260 KB Output is correct
11 Correct 2 ms 1876 KB Output is correct
12 Correct 4 ms 2644 KB Output is correct
13 Incorrect 3 ms 2516 KB Output isn't correct
14 Incorrect 3 ms 2516 KB Output isn't correct
15 Incorrect 10 ms 4296 KB Output isn't correct
16 Incorrect 11 ms 4264 KB Output isn't correct
17 Incorrect 9 ms 4108 KB Output isn't correct
18 Correct 8 ms 4464 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30172 KB Output is correct
2 Correct 44 ms 10068 KB Output is correct
3 Correct 260 ms 31680 KB Output is correct
4 Correct 67 ms 15080 KB Output is correct
5 Incorrect 218 ms 23832 KB Output isn't correct
6 Incorrect 756 ms 51864 KB Output isn't correct
7 Incorrect 16 ms 31572 KB Output isn't correct
8 Correct 18 ms 30184 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Correct 16 ms 31068 KB Output is correct
12 Incorrect 1 ms 1492 KB Output isn't correct
13 Correct 43 ms 10108 KB Output is correct
14 Incorrect 30 ms 7396 KB Output isn't correct
15 Correct 25 ms 8148 KB Output is correct
16 Correct 20 ms 3508 KB Output is correct
17 Correct 125 ms 16160 KB Output is correct
18 Correct 94 ms 15996 KB Output is correct
19 Correct 67 ms 15104 KB Output is correct
20 Incorrect 61 ms 14028 KB Output isn't correct
21 Incorrect 156 ms 24592 KB Output isn't correct
22 Incorrect 219 ms 23952 KB Output isn't correct
23 Incorrect 237 ms 19948 KB Output isn't correct
24 Incorrect 175 ms 24744 KB Output isn't correct
25 Incorrect 406 ms 31780 KB Output isn't correct
26 Correct 357 ms 27788 KB Output is correct
27 Correct 521 ms 34916 KB Output is correct
28 Incorrect 720 ms 51872 KB Output isn't correct
29 Correct 673 ms 48628 KB Output is correct
30 Correct 618 ms 46164 KB Output is correct
31 Correct 562 ms 26192 KB Output is correct
32 Incorrect 553 ms 33180 KB Output isn't correct