oj.uz

Submission #1049421

# Submission time Handle Problem Language Result Execution time Memory
1049421 2024-08-08T18:15:56 Z DeathIsAwe Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 814 ms 160752 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] == 'G') {
                    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
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 15448 KB Output isn't correct
2 Incorrect 0 ms 4444 KB Output isn't correct
3 Correct 1 ms 4544 KB Output is correct
4 Incorrect 9 ms 15388 KB Output isn't correct
5 Incorrect 3 ms 10844 KB Output isn't correct
6 Incorrect 0 ms 4444 KB Output isn't correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4548 KB Output is correct
9 Incorrect 1 ms 4544 KB Output isn't correct
10 Incorrect 2 ms 10588 KB Output isn't correct
11 Correct 3 ms 8796 KB Output is correct
12 Incorrect 5 ms 10844 KB Output isn't correct
13 Incorrect 4 ms 10588 KB Output isn't correct
14 Incorrect 3 ms 10588 KB Output isn't correct
15 Incorrect 13 ms 15196 KB Output isn't correct
16 Incorrect 14 ms 15452 KB Output isn't correct
17 Incorrect 10 ms 14940 KB Output isn't correct
18 Incorrect 11 ms 15448 KB Output isn't correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 96856 KB Output is correct
2 Incorrect 41 ms 34844 KB Output isn't correct
3 Incorrect 367 ms 118872 KB Output isn't correct
4 Incorrect 108 ms 53300 KB Output isn't correct
5 Correct 285 ms 85204 KB Output is correct
6 Incorrect 814 ms 147376 KB Output isn't correct
7 Incorrect 8 ms 103000 KB Output isn't correct
8 Correct 8 ms 96820 KB Output is correct
9 Incorrect 3 ms 4700 KB Output isn't correct
10 Incorrect 1 ms 2648 KB Output isn't correct
11 Incorrect 9 ms 98912 KB Output isn't correct
12 Incorrect 1 ms 6656 KB Output isn't correct
13 Incorrect 38 ms 34880 KB Output isn't correct
14 Incorrect 33 ms 25940 KB Output isn't correct
15 Incorrect 25 ms 27996 KB Output isn't correct
16 Incorrect 16 ms 13400 KB Output isn't correct
17 Incorrect 96 ms 57680 KB Output isn't correct
18 Incorrect 93 ms 55608 KB Output isn't correct
19 Incorrect 129 ms 53284 KB Output isn't correct
20 Incorrect 86 ms 48980 KB Output isn't correct
21 Incorrect 212 ms 87608 KB Output isn't correct
22 Correct 276 ms 85096 KB Output is correct
23 Incorrect 274 ms 71764 KB Output isn't correct
24 Incorrect 210 ms 89328 KB Output isn't correct
25 Incorrect 371 ms 118760 KB Output isn't correct
26 Correct 282 ms 100720 KB Output is correct
27 Correct 723 ms 154560 KB Output is correct
28 Incorrect 795 ms 145568 KB Output isn't correct
29 Incorrect 765 ms 144600 KB Output isn't correct
30 Incorrect 740 ms 160752 KB Output isn't correct
31 Incorrect 562 ms 93304 KB Output isn't correct
32 Incorrect 676 ms 154416 KB Output isn't correct