oj.uz

Submission #811972

# Submission time Handle Problem Language Result Execution time Memory
811972 2023-08-07T06:38:32 Z makanhulia Tracks in the Snow (BOI13_tracks) C++17
50.5208 / 100
 709 ms 66296 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 12 ms 4564 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 4500 KB Output is correct
5 Incorrect 3 ms 2644 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 3 ms 2004 KB Output is correct
12 Correct 5 ms 2644 KB Output is correct
13 Incorrect 3 ms 2648 KB Output isn't correct
14 Incorrect 3 ms 2644 KB Output isn't correct
15 Incorrect 12 ms 4552 KB Output isn't correct
16 Incorrect 11 ms 4532 KB Output isn't correct
17 Incorrect 9 ms 4308 KB Output isn't correct
18 Correct 7 ms 4572 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30208 KB Output is correct
2 Correct 46 ms 11676 KB Output is correct
3 Correct 269 ms 46328 KB Output is correct
4 Correct 71 ms 18688 KB Output is correct
5 Incorrect 224 ms 32632 KB Output isn't correct
6 Incorrect 709 ms 66296 KB Output isn't correct
7 Incorrect 15 ms 31700 KB Output isn't correct
8 Correct 15 ms 30292 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 15 ms 31072 KB Output is correct
12 Incorrect 1 ms 1492 KB Output isn't correct
13 Correct 44 ms 11676 KB Output is correct
14 Incorrect 26 ms 8312 KB Output isn't correct
15 Correct 23 ms 9056 KB Output is correct
16 Correct 20 ms 4052 KB Output is correct
17 Correct 118 ms 20120 KB Output is correct
18 Correct 90 ms 19908 KB Output is correct
19 Correct 67 ms 18708 KB Output is correct
20 Incorrect 64 ms 17440 KB Output isn't correct
21 Incorrect 169 ms 33612 KB Output isn't correct
22 Incorrect 221 ms 32584 KB Output isn't correct
23 Incorrect 236 ms 27512 KB Output isn't correct
24 Incorrect 174 ms 33624 KB Output isn't correct
25 Incorrect 405 ms 42920 KB Output isn't correct
26 Correct 353 ms 39480 KB Output is correct
27 Correct 520 ms 48376 KB Output is correct
28 Incorrect 701 ms 65572 KB Output isn't correct
29 Correct 691 ms 60004 KB Output is correct
30 Correct 625 ms 59232 KB Output is correct
31 Correct 524 ms 35624 KB Output is correct
32 Incorrect 510 ms 46332 KB Output isn't correct