Submission #742525

#	Time	Username	Problem	Language	Result	Execution time	Memory
742525		bogdanvladmihai	T-Covering (eJOI19_covering)	C++14	100 / 100	268 ms	15948 KiB

covering

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 30 / 30