Submission #513998

#	Time	Username	Problem	Language	Result	Execution time	Memory
513998		KoD	Selotejp (COCI20_selotejp)	C++17	110 / 110	47 ms	1868 KiB

Main

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
    explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector grid(N, vector<char>(M));
    for (auto& v : grid) {
        for (auto& x : v) {
            std::cin >> x;
        }
    }
    const int V = N * M + 2;
    const int src = N * M + 0;
    const int dst = N * M + 1;
    struct Edge {
        int to, cap, rev;
    };
    vector<vector<Edge>> graph(V);
    const auto add_edge = [&](const int u, const int v, const int f) {
        graph[u].push_back(Edge{v, f, (int)graph[v].size()});
        graph[v].push_back(Edge{u, 0, (int)graph[u].size() - 1});
    };
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (grid[i][j] == '#') {
                ans += 1;
                if (i + 1 < N and grid[i + 1][j] == '#') {
                    ans -= 1;
                    const int u = i * M + j;
                    const int v = u + M;
                    add_edge(u, dst, 1);
                    add_edge(v, u, 1);
                }
                if (j + 1 < M and grid[i][j + 1] == '#') {
                    ans -= 1;
                    const int u = i * M + j;
                    const int v = u + 1;
                    add_edge(src, u, 1);
                    add_edge(u, v, 1);
                }
            }
        }
    }
    vector<char> done(V);
    const auto dfs = RecLambda([&](auto&& dfs, const int u) -> bool {
        if (u == dst) return true;
        if (done[u]) return false;
        done[u] = true;
        for (auto& [v, c, r] : graph[u]) {
            if (c == 0) continue;
            if (dfs(v)) {
                c -= 1;
                graph[v][r].cap += 1;
                return true;
            }
        }
        return false;
    });
    while (true) {
        std::fill(done.begin(), done.end(), false);
        if (dfs(src)) {
            ans += 1;
        } else {
            break;
        }
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40