oj.uz

답안 #892786

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
892786 2023-12-26T00:18:03 Z cogentcoder73 Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 2000 ms 423308 KB 
#include <bits/stdc++.h>
using namespace std;

int H, W;

vector<pair<int, int>> bfs(vector<vector<char>>& meadow, vector<vector<bool>>& visited, pair<int, int> start, char find, bool avoid) {
    vector<pair<int, int>> cc;
    queue<pair<int, int>> q; q.push(start);
    pair<int, int> cur;
    while (!q.empty()) {
        cur = q.front(); q.pop();
        if (!visited[cur.first][cur.second]) {
            visited[cur.first][cur.second] = true;
            if ((avoid && meadow[cur.first][cur.second] != find) || (!avoid && meadow[cur.first][cur.second] == find)) {
                cc.push_back(cur);
                if (cur.first > 0) q.push({cur.first - 1, cur.second});
                if (cur.first < H - 1) q.push({cur.first + 1, cur.second});
                if (cur.second > 0) q.push({cur.first, cur.second - 1});
                if (cur.second < W - 1) q.push({cur.first, cur.second + 1});
            }
        }
    }
    return cc;
}

int main() {
    cin >> H >> W;
    vector<vector<char>> meadow(H, vector<char>(W));
    for (int h = 0; h < H; h++) for (int w = 0; w < W; w++) cin >> meadow[h][w];
    vector<vector<bool>> visited(H, vector<bool>(W, false));

    vector<vector<pair<int, int>>> ccs;
    int numC = 0;
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (!visited[h][w] && meadow[h][w] != '.') {
                ccs.push_back(bfs(meadow, visited, {h, w}, '.', true));
            }
        }
    }

    vector<vector<bool>> visitedR(H, vector<bool>(W, false));
    vector<vector<bool>> visitedF(H, vector<bool>(W, false));

    int curR, curF;
    int ans = 0;

    for (vector<pair<int, int>> cc : ccs) {
        curR = 0;
        curF = 0;
        for (pair<int, int> p : cc) {
            if (!visitedR[p.first][p.second] && meadow[p.first][p.second] == 'R') {
                curR++;
                bfs(meadow, visitedR, p, 'R', false);
            }
            if (!visitedF[p.first][p.second] && meadow[p.first][p.second] == 'F') {
                curF++;
                bfs(meadow, visitedF, p, 'F', false);
            }
        }
        if (curR == 0 || curF == 0)  ans++;
        else ans += 1 + min(curR, curF);
    }

    cout << ans << "\n";
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:33:9: warning: unused variable 'numC' [-Wunused-variable]
   33 |     int numC = 0;
      |         ^~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 4880 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 21 ms 4004 KB Output isn't correct
5 Incorrect 6 ms 992 KB Output isn't correct
6 Incorrect 0 ms 344 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 6 ms 1152 KB Output isn't correct
11 Incorrect 6 ms 1504 KB Output isn't correct
12 Incorrect 13 ms 2008 KB Output isn't correct
13 Incorrect 6 ms 992 KB Output isn't correct
14 Incorrect 6 ms 940 KB Output isn't correct
15 Incorrect 32 ms 3896 KB Output isn't correct
16 Incorrect 36 ms 4740 KB Output isn't correct
17 Incorrect 24 ms 2768 KB Output isn't correct
18 Incorrect 21 ms 4192 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 1884 KB Output isn't correct
2 Incorrect 142 ms 14724 KB Output isn't correct
3 Incorrect 1016 ms 95904 KB Output isn't correct
4 Incorrect 219 ms 18616 KB Output isn't correct
5 Incorrect 891 ms 91920 KB Output isn't correct
6 Execution timed out 2045 ms 340824 KB Time limit exceeded
7 Incorrect 4 ms 1624 KB Output isn't correct
8 Incorrect 5 ms 1628 KB Output isn't correct
9 Incorrect 6 ms 936 KB Output isn't correct
10 Incorrect 2 ms 600 KB Output isn't correct
11 Incorrect 4 ms 1628 KB Output isn't correct
12 Incorrect 3 ms 700 KB Output isn't correct
13 Incorrect 139 ms 16416 KB Output isn't correct
14 Incorrect 80 ms 9152 KB Output isn't correct
15 Incorrect 69 ms 7384 KB Output isn't correct
16 Incorrect 73 ms 7596 KB Output isn't correct
17 Incorrect 355 ms 36260 KB Output isn't correct
18 Incorrect 272 ms 28080 KB Output isn't correct
19 Incorrect 218 ms 19688 KB Output isn't correct
20 Incorrect 234 ms 22928 KB Output isn't correct
21 Incorrect 605 ms 56444 KB Output isn't correct
22 Incorrect 892 ms 90660 KB Output isn't correct
23 Incorrect 700 ms 69036 KB Output isn't correct
24 Incorrect 669 ms 68204 KB Output isn't correct
25 Incorrect 1167 ms 107680 KB Output isn't correct
26 Correct 1564 ms 351796 KB Output is correct
27 Execution timed out 2013 ms 423308 KB Time limit exceeded
28 Execution timed out 2062 ms 341908 KB Time limit exceeded
29 Execution timed out 2009 ms 341512 KB Time limit exceeded
30 Execution timed out 2047 ms 334156 KB Time limit exceeded
31 Incorrect 1583 ms 183544 KB Output isn't correct
32 Incorrect 1803 ms 309884 KB Output isn't correct