oj.uz

Submission #742525

# Submission time Handle Problem Language Result Execution time Memory
742525 2023-05-16T11:37:55 Z bogdanvladmihai T-Covering (eJOI19_covering) C++14
100 / 100
 268 ms 15948 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <limits.h>
#include <queue>

const std::vector<std::pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

inline bool inside(const std::pair<int, int> &point, int N, int M) {
    return point.first >= 0 && point.second >= 0 && point.first < N && point.second < M;
}

int main() {
    int N, M, K;
    std::cin >> N >> M;
    std::vector<std::vector<int>> mat(N, std::vector<int>(M));
    for (auto &line : mat) {
        for (int &x : line) {
            std::cin >> x;
        }
    }
    std::cin >> K;
    std::vector<std::vector<bool>> red(N, std::vector<bool>(M));
    for (int i = 0; i < K; i++) {
        int x, y;
        std::cin >> x >> y;
        red[x][y] = true;
    }
    std::vector<std::vector<int>> color(N, std::vector<int>(M, -1));
    std::vector<std::vector<bool>> used(N, std::vector<bool>(M));
    std::vector<int> erase, sum, difference;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!used[i][j] && red[i][j]) {
                std::queue<std::pair<int, int>> Q;
                Q.emplace(i, j);
                color[i][j] = erase.size();
                erase.push_back(INT_MAX);
                sum.push_back(0);
                difference.push_back(0);
                used[i][j] = true;
                while (!Q.empty()) {
                    std::pair<int, int> curr = Q.front();
                    Q.pop();
                    difference.back() += (red[curr.first][curr.second] ? -3 : 1);
                    sum.back() += mat[curr.first][curr.second];
                    if (!red[curr.first][curr.second]) {
                        erase.back() = std::min(erase.back(), mat[curr.first][curr.second]);
                    }
                    for (const std::pair<int, int> &dir : dirs) {
                        std::pair<int, int> next = {dir.first + curr.first, dir.second + curr.second};
                        if (inside(next, N, M) && !used[next.first][next.second] && (red[curr.first][curr.second] || red[next.first][next.second])) {
                            color[next.first][next.second] = color[curr.first][curr.second];
                            used[next.first][next.second] = true;
                            Q.push(next);
                        }
                    }
                }
            }
        }
    }
    int answer = 0;
    for (size_t i = 0; i < erase.size(); i++) {
        if (difference[i] < 0) {
            std::cout << "No\n";
            return 0;
        }
        answer += sum[i] - erase[i] * (difference[i] > 0);
    }
    std::cout << answer << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 7 ms 692 KB Output is correct
3 Correct 20 ms 1460 KB Output is correct
4 Correct 57 ms 3900 KB Output is correct
5 Correct 201 ms 12284 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 21 ms 1456 KB Output is correct
4 Correct 60 ms 3904 KB Output is correct
5 Correct 206 ms 12276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 9 ms 696 KB Output is correct
3 Correct 25 ms 1440 KB Output is correct
4 Correct 66 ms 3900 KB Output is correct
5 Correct 199 ms 12272 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 21 ms 1480 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 7 ms 692 KB Output is correct
3 Correct 20 ms 1460 KB Output is correct
4 Correct 57 ms 3900 KB Output is correct
5 Correct 201 ms 12284 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 6 ms 724 KB Output is correct
8 Correct 21 ms 1456 KB Output is correct
9 Correct 60 ms 3904 KB Output is correct
10 Correct 206 ms 12276 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 9 ms 696 KB Output is correct
13 Correct 25 ms 1440 KB Output is correct
14 Correct 66 ms 3900 KB Output is correct
15 Correct 199 ms 12272 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 11 ms 852 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 21 ms 1480 KB Output is correct
21 Correct 3 ms 376 KB Output is correct
22 Correct 9 ms 768 KB Output is correct
23 Correct 21 ms 1468 KB Output is correct
24 Correct 59 ms 3916 KB Output is correct
25 Correct 211 ms 12296 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 7 ms 692 KB Output is correct
3 Correct 20 ms 1460 KB Output is correct
4 Correct 57 ms 3900 KB Output is correct
5 Correct 201 ms 12284 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 6 ms 724 KB Output is correct
8 Correct 21 ms 1456 KB Output is correct
9 Correct 60 ms 3904 KB Output is correct
10 Correct 206 ms 12276 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 9 ms 696 KB Output is correct
13 Correct 25 ms 1440 KB Output is correct
14 Correct 66 ms 3900 KB Output is correct
15 Correct 199 ms 12272 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 11 ms 852 KB Output is correct
19 Correct 7 ms 596 KB Output is correct
20 Correct 21 ms 1480 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 9 ms 768 KB Output is correct
28 Correct 21 ms 1468 KB Output is correct
29 Correct 59 ms 3916 KB Output is correct
30 Correct 211 ms 12296 KB Output is correct
31 Correct 268 ms 12840 KB Output is correct
32 Correct 199 ms 12124 KB Output is correct
33 Correct 216 ms 15948 KB Output is correct
34 Correct 194 ms 12124 KB Output is correct
35 Correct 214 ms 12844 KB Output is correct