oj.uz

Submission #811977

# Submission time Handle Problem Language Result Execution time Memory
811977 2023-08-07T06:40:01 Z andecaandeci Tracks in the Snow (BOI13_tracks) C++17
50.5208 / 100
 889 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 15 ms 4296 KB Output isn't correct
2 Incorrect 1 ms 488 KB Output isn't correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 8 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 2304 KB Output is correct
11 Correct 4 ms 1876 KB Output is correct
12 Correct 6 ms 2676 KB Output is correct
13 Incorrect 3 ms 2516 KB Output isn't correct
14 Incorrect 4 ms 2516 KB Output isn't correct
15 Incorrect 12 ms 4308 KB Output isn't correct
16 Incorrect 12 ms 4204 KB Output isn't correct
17 Incorrect 11 ms 4108 KB Output isn't correct
18 Correct 9 ms 4436 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30164 KB Output is correct
2 Correct 47 ms 10048 KB Output is correct
3 Correct 370 ms 31684 KB Output is correct
4 Correct 77 ms 15104 KB Output is correct
5 Incorrect 283 ms 23836 KB Output isn't correct
6 Incorrect 889 ms 51868 KB Output isn't correct
7 Incorrect 18 ms 31572 KB Output isn't correct
8 Correct 21 ms 30296 KB Output is correct
9 Incorrect 2 ms 468 KB Output isn't correct
10 Incorrect 1 ms 360 KB Output isn't correct
11 Correct 19 ms 31056 KB Output is correct
12 Incorrect 2 ms 1492 KB Output isn't correct
13 Correct 50 ms 10064 KB Output is correct
14 Incorrect 28 ms 7496 KB Output isn't correct
15 Correct 29 ms 8076 KB Output is correct
16 Correct 23 ms 3488 KB Output is correct
17 Correct 138 ms 16160 KB Output is correct
18 Correct 104 ms 16000 KB Output is correct
19 Correct 78 ms 15100 KB Output is correct
20 Incorrect 71 ms 14080 KB Output isn't correct
21 Incorrect 192 ms 24548 KB Output isn't correct
22 Incorrect 248 ms 23752 KB Output isn't correct
23 Incorrect 263 ms 19992 KB Output isn't correct
24 Incorrect 185 ms 24744 KB Output isn't correct
25 Incorrect 474 ms 31628 KB Output isn't correct
26 Correct 339 ms 27788 KB Output is correct
27 Correct 482 ms 34924 KB Output is correct
28 Incorrect 777 ms 51872 KB Output isn't correct
29 Correct 831 ms 48624 KB Output is correct
30 Correct 620 ms 46160 KB Output is correct
31 Correct 669 ms 26260 KB Output is correct
32 Incorrect 517 ms 33144 KB Output isn't correct