oj.uz

Submission #368097

# Submission time Handle Problem Language Result Execution time Memory
368097 2021-02-19T13:36:58 Z R3KT Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1754 ms 51464 KB 
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <string.h>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
using namespace std;
typedef long long ll;

const int MaxN = 4e3;
int h, w;
char arr[MaxN][MaxN];
bool visited[MaxN][MaxN];
queue<pair<int, int>> temp;

bool dfs(char type) {
    queue<pair<int, int>> q;
    while (!temp.empty()) {
        q.push(temp.front());
        temp.pop();
    }
    int count=0;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        // if (cur.first < 0 || cur.second < 0 || cur.first >= h || cur.second >= w) continue;
        if (visited[cur.first][cur.second]) continue;
        if (arr[x][y] != type) {
            temp.push({x, y});
            continue;
        }
        visited[x][y] = true;
        count++;
        if (x+1 >= 0 && y >= 0 && x+1 < h && y < w && !visited[x+1][y] && arr[x+1][y] != '.') {
            q.push({x+1, y});
        }
        if (x-1 >= 0 && y >= 0 && x-1 < h && y < w && !visited[x-1][y] && arr[x-1][y] != '.') {
            q.push({x-1, y});
        }
        if (x >= 0 && y+1 >= 0 && x < h && y+1 < w && !visited[x][y+1] && arr[x][y+1] != '.') {
            q.push({x, y+1});
        }
        if (x >= 0 && y-1 >= 0 && x < h && y-1 < w && !visited[x][y-1] && arr[x][y-1] != '.') {
            q.push({x, y-1});
        }
    }
    return count != 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> h >> w;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            cin >> arr[i][j];
        }
    }    

    bool fox = false;
    if (arr[0][0] == 'F') fox = true;

    temp.push({0,0});
    int count=0;
    while (true) {
        char type = 'F';
        if (!fox) type = 'R';
        if (!dfs(type)) break;
        count++;
        fox = !fox;
    }    

    cout << count;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4588 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 14 ms 4588 KB Output is correct
5 Correct 5 ms 2668 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 1024 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 4 ms 2412 KB Output is correct
11 Correct 4 ms 2028 KB Output is correct
12 Correct 12 ms 2796 KB Output is correct
13 Correct 6 ms 2668 KB Output is correct
14 Correct 5 ms 2668 KB Output is correct
15 Correct 21 ms 4588 KB Output is correct
16 Correct 25 ms 4588 KB Output is correct
17 Correct 16 ms 4332 KB Output is correct
18 Correct 13 ms 4588 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30316 KB Output is correct
2 Correct 89 ms 11628 KB Output is correct
3 Correct 481 ms 33644 KB Output is correct
4 Correct 144 ms 16876 KB Output is correct
5 Correct 573 ms 26220 KB Output is correct
6 Correct 1679 ms 51464 KB Output is correct
7 Correct 22 ms 31724 KB Output is correct
8 Correct 26 ms 30316 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 24 ms 31084 KB Output is correct
12 Correct 3 ms 1516 KB Output is correct
13 Correct 86 ms 11628 KB Output is correct
14 Correct 49 ms 8428 KB Output is correct
15 Correct 37 ms 9196 KB Output is correct
16 Correct 47 ms 4204 KB Output is correct
17 Correct 229 ms 18412 KB Output is correct
18 Correct 170 ms 18156 KB Output is correct
19 Correct 118 ms 17388 KB Output is correct
20 Correct 123 ms 16108 KB Output is correct
21 Correct 277 ms 26816 KB Output is correct
22 Correct 603 ms 24460 KB Output is correct
23 Correct 466 ms 20436 KB Output is correct
24 Correct 388 ms 25196 KB Output is correct
25 Correct 550 ms 33776 KB Output is correct
26 Correct 664 ms 28752 KB Output is correct
27 Correct 1030 ms 35780 KB Output is correct
28 Correct 1754 ms 50272 KB Output is correct
29 Correct 1605 ms 46380 KB Output is correct
30 Correct 1566 ms 44804 KB Output is correct
31 Correct 1492 ms 26348 KB Output is correct
32 Correct 799 ms 33900 KB Output is correct