oj.uz

Submission #138359

# Submission time Handle Problem Language Result Execution time Memory
138359 2019-07-29T19:51:56 Z silxikys Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 2000 ms 137600 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 4005;
int H, W;
char grid[maxn][maxn];
bool seen[maxn][maxn];

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

bool valid(int x, int y) {
    return 0 <= x && x < H && 0 <= y && y < W;
}

bool cnt(pair<int,int>& p, char curr) {
    for (int k = 0; k < 4; k++) {
        int nx = p.first + dx[k];
        int ny = p.first + dy[k];
        if (!seen[nx][ny] && valid(nx,ny) && grid[nx][ny] == (curr=='R'?'F':'R')) return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> grid[i][j];
        }
    }
    if (H == 1 && W == 1) {
        cout << 1 << '\n';
        return 0;
    }
    queue<pair<int,int>> q, nxt;
    q.push({0,0});
    seen[0][0] = true;
    char curr = grid[0][0];
    int ans = 0;
    while (true) {
        int added = 0;
        //cout << "level " << ans << '\n';
        //cout << q.size() << '\n';
        while (!q.empty()) {
            auto p = q.front(); q.pop();
            nxt.push(p);
            //cout << p.first << ' ' << p.second << '\n';
            for (int k = 0; k < 4; k++) {
                int nx = p.first + dx[k];
                int ny = p.second + dy[k];
                if (!valid(nx,ny)) continue;
                if (seen[nx][ny]) continue;
                if (grid[nx][ny] != curr) continue;
                seen[nx][ny] = true;
                q.push({nx,ny});
                added++;
            }
        }
        while (!nxt.empty()) {
            auto p = nxt.front(); nxt.pop();
            if (cnt(p,curr)) q.push(p);
        }
        /*
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                cout << seen[i][j];
            }
            cout << '\n';
        }
        */
        curr = curr == 'R' ? 'F' : 'R';
        if (added == 0) break;
        ans++;
    }
    cout << ans << '\n';
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4600 KB Output isn't correct
2 Incorrect 2 ms 508 KB Output isn't correct
3 Incorrect 2 ms 760 KB Output isn't correct
4 Incorrect 19 ms 5240 KB Output isn't correct
5 Incorrect 6 ms 2680 KB Output isn't correct
6 Incorrect 2 ms 504 KB Output isn't correct
7 Incorrect 2 ms 760 KB Output isn't correct
8 Incorrect 3 ms 888 KB Output isn't correct
9 Incorrect 3 ms 1144 KB Output isn't correct
10 Incorrect 5 ms 2424 KB Output isn't correct
11 Incorrect 7 ms 2168 KB Output isn't correct
12 Incorrect 7 ms 2808 KB Output isn't correct
13 Incorrect 6 ms 2680 KB Output isn't correct
14 Incorrect 6 ms 2680 KB Output isn't correct
15 Incorrect 12 ms 4572 KB Output isn't correct
16 Incorrect 14 ms 4600 KB Output isn't correct
17 Incorrect 11 ms 4344 KB Output isn't correct
18 Incorrect 17 ms 5240 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 30328 KB Output isn't correct
2 Incorrect 38 ms 11768 KB Output isn't correct
3 Incorrect 267 ms 34824 KB Output isn't correct
4 Incorrect 74 ms 18808 KB Output isn't correct
5 Incorrect 153 ms 27504 KB Output isn't correct
6 Incorrect 1521 ms 112148 KB Output isn't correct
7 Incorrect 38 ms 31736 KB Output isn't correct
8 Incorrect 38 ms 30328 KB Output isn't correct
9 Incorrect 4 ms 632 KB Output isn't correct
10 Incorrect 3 ms 504 KB Output isn't correct
11 Incorrect 39 ms 31196 KB Output isn't correct
12 Incorrect 3 ms 1528 KB Output isn't correct
13 Incorrect 38 ms 11728 KB Output isn't correct
14 Incorrect 28 ms 8440 KB Output isn't correct
15 Incorrect 24 ms 9208 KB Output isn't correct
16 Incorrect 476 ms 4728 KB Output isn't correct
17 Incorrect 87 ms 19960 KB Output isn't correct
18 Incorrect 75 ms 19832 KB Output isn't correct
19 Incorrect 77 ms 18852 KB Output isn't correct
20 Incorrect 69 ms 17528 KB Output isn't correct
21 Incorrect 165 ms 28332 KB Output isn't correct
22 Incorrect 152 ms 27384 KB Output isn't correct
23 Execution timed out 2023 ms 25468 KB Time limit exceeded
24 Incorrect 158 ms 28280 KB Output isn't correct
25 Incorrect 262 ms 34752 KB Output isn't correct
26 Correct 1008 ms 131228 KB Output is correct
27 Incorrect 1456 ms 123496 KB Output isn't correct
28 Incorrect 1632 ms 112208 KB Output isn't correct
29 Incorrect 1525 ms 105020 KB Output isn't correct
30 Incorrect 1486 ms 135736 KB Output isn't correct
31 Incorrect 214 ms 29708 KB Output isn't correct
32 Incorrect 1214 ms 137600 KB Output isn't correct