oj.uz

Submission #811989

# Submission time Handle Problem Language Result Execution time Memory
811989 2023-08-07T06:42:19 Z hanifchdn Tracks in the Snow (BOI13_tracks) C++17
50.5208 / 100
 746 ms 51812 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 11 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 3 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 5 ms 2672 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 4304 KB Output isn't correct
16 Incorrect 11 ms 4248 KB Output isn't correct
17 Incorrect 10 ms 4180 KB Output isn't correct
18 Correct 7 ms 4468 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 30164 KB Output is correct
2 Correct 43 ms 10152 KB Output is correct
3 Correct 264 ms 31680 KB Output is correct
4 Correct 68 ms 15060 KB Output is correct
5 Incorrect 224 ms 23832 KB Output isn't correct
6 Incorrect 708 ms 51812 KB Output isn't correct
7 Incorrect 21 ms 31572 KB Output isn't correct
8 Correct 16 ms 30164 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 31060 KB Output is correct
12 Incorrect 1 ms 1472 KB Output isn't correct
13 Correct 43 ms 10084 KB Output is correct
14 Incorrect 25 ms 7460 KB Output isn't correct
15 Correct 22 ms 8048 KB Output is correct
16 Correct 20 ms 3412 KB Output is correct
17 Correct 116 ms 16120 KB Output is correct
18 Correct 91 ms 15936 KB Output is correct
19 Correct 69 ms 15076 KB Output is correct
20 Incorrect 63 ms 13972 KB Output isn't correct
21 Incorrect 159 ms 24636 KB Output isn't correct
22 Incorrect 215 ms 23776 KB Output isn't correct
23 Incorrect 236 ms 19992 KB Output isn't correct
24 Incorrect 169 ms 24740 KB Output isn't correct
25 Incorrect 398 ms 31672 KB Output isn't correct
26 Correct 347 ms 27724 KB Output is correct
27 Correct 505 ms 34916 KB Output is correct
28 Incorrect 724 ms 51788 KB Output isn't correct
29 Correct 746 ms 48632 KB Output is correct
30 Correct 615 ms 46168 KB Output is correct
31 Correct 547 ms 26256 KB Output is correct
32 Incorrect 538 ms 33040 KB Output isn't correct