oj.uz

Submission #1049422

# Submission time Handle Problem Language Result Execution time Memory
1049422 2024-08-08T18:17:09 Z DeathIsAwe Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 868 ms 222124 KB 
#include <bits/stdc++.h>
using namespace std;
char grid[5000][5000];
int visited[5000][5000];
vector<pair<int,int>> foxtrack, rabtrack;


void floodfill(vector<pair<int,int>> &track, int h, int w) {
    pair<int,int> block;
    while (track.size() > 0) {
        block = track[track.size() - 1]; track.pop_back();
        visited[block.first][block.second] = true;
        //cout << block.first << ' ' << block.second << '\n';
        if (block.first > 0) {
            if (!visited[block.first - 1][block.second]) {
                if (grid[block.first - 1][block.second] == 'F') {
                    foxtrack.push_back(make_pair(block.first - 1, block.second));
                } else if (grid[block.first - 1][block.second] == 'R') {
                    rabtrack.push_back(make_pair(block.first - 1, block.second));
                }
            }
        }
        if (block.first < h - 1) {
            if (!visited[block.first + 1][block.second]) {
                if (grid[block.first + 1][block.second] == 'F') {
                    foxtrack.push_back(make_pair(block.first + 1, block.second));
                } else if (grid[block.first + 1][block.second] == 'R') {
                    rabtrack.push_back(make_pair(block.first + 1, block.second));
                }
            }
        }
        if (block.second > 0) {
            if (!visited[block.first][block.second - 1]) {
                if (grid[block.first][block.second - 1] == 'F') {
                    foxtrack.push_back(make_pair(block.first, block.second - 1));
                } else if (grid[block.first][block.second - 1] == 'R') {
                    rabtrack.push_back(make_pair(block.first, block.second - 1));
                }
            }
        }
        if (block.second < w - 1) {
            if (!visited[block.first][block.second + 1]) {
                if (grid[block.first][block.second + 1] == 'F') {
                    foxtrack.push_back(make_pair(block.first, block.second + 1));
                } else if (grid[block.first][block.second + 1] == 'R') {
                    rabtrack.push_back(make_pair(block.first, block.second + 1));
                }
            }
        }
    }
}


int main() {
    int h, w; cin >> h >> w;
    for (int i=0;i<h;i++) {
        for (int j=0;j<w;j++) {
            cin >> grid[i][j];
            visited[i][j] = false;
        }
    }

    char animal = grid[0][0];
    int ans = 0;    
    pair<int,int> block;
    if (grid[0][0] == 'F') {
        foxtrack.push_back(make_pair(0, 0));
    } else {
        rabtrack.push_back(make_pair(0, 0));
    }
    while (true) {
        if (animal == 'F') {
            if (foxtrack.size() == 0) {
                break;
            }
            floodfill(foxtrack, h, w);
            animal = 'R';
        } else {
            if (rabtrack.size() == 0) {
                break;
            }
            floodfill(rabtrack, h, w);
            animal = 'F';
        }
        ans++;
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15316 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Correct 9 ms 15384 KB Output is correct
5 Correct 3 ms 10760 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 0 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 4 ms 10584 KB Output is correct
11 Correct 3 ms 9008 KB Output is correct
12 Correct 6 ms 11040 KB Output is correct
13 Correct 4 ms 10588 KB Output is correct
14 Correct 3 ms 10588 KB Output is correct
15 Correct 13 ms 14940 KB Output is correct
16 Correct 15 ms 15320 KB Output is correct
17 Correct 11 ms 14972 KB Output is correct
18 Correct 9 ms 15544 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 96856 KB Output is correct
2 Correct 59 ms 33312 KB Output is correct
3 Correct 463 ms 102996 KB Output is correct
4 Correct 108 ms 49744 KB Output is correct
5 Correct 278 ms 76372 KB Output is correct
6 Correct 820 ms 168600 KB Output is correct
7 Correct 10 ms 103000 KB Output is correct
8 Correct 8 ms 96860 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 9 ms 98908 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 57 ms 33316 KB Output is correct
14 Correct 33 ms 25168 KB Output is correct
15 Correct 32 ms 26968 KB Output is correct
16 Correct 27 ms 12960 KB Output is correct
17 Correct 165 ms 53840 KB Output is correct
18 Correct 116 ms 51784 KB Output is correct
19 Correct 107 ms 49712 KB Output is correct
20 Correct 102 ms 45648 KB Output is correct
21 Correct 269 ms 78420 KB Output is correct
22 Correct 262 ms 76368 KB Output is correct
23 Correct 300 ms 64340 KB Output is correct
24 Correct 256 ms 80464 KB Output is correct
25 Correct 425 ms 103032 KB Output is correct
26 Correct 572 ms 222124 KB Output is correct
27 Correct 716 ms 142240 KB Output is correct
28 Correct 868 ms 168964 KB Output is correct
29 Correct 818 ms 164924 KB Output is correct
30 Correct 766 ms 154436 KB Output is correct
31 Correct 584 ms 85828 KB Output is correct
32 Correct 695 ms 176824 KB Output is correct