제출 #1247946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247946		dfhdfhdsf	Selotejp (COCI20_selotejp)	C++20	35 / 110	1 ms	584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define isz(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()

const int INF = 1e9;

// Hopcroft–Karp trên đồ thị L (1..nL) – R (1..nR)
struct HopcroftKarp {
    int nL, nR;
    vector<vector<int>> adj;
    vector<int> dist, pairU, pairV;
    HopcroftKarp(int _nL, int _nR)
        : nL(_nL), nR(_nR),
          adj(_nL+1), dist(_nL+1),
          pairU(_nL+1), pairV(_nR+1) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
    }

    bool bfs() {
        queue<int> q;
        FOR(u,1,nL) {
            if (pairU[u] == 0) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INF;
            }
        }
        dist[0] = INF;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (dist[u] < dist[0]) {
                for (int v: adj[u]) {
                    if (dist[pairV[v]] == INF) {
                        dist[pairV[v]] = dist[u] + 1;
                        q.push(pairV[v]);
                    }
                }
            }
        }
        return dist[0] != INF;
    }

    bool dfs(int u) {
        if (u == 0) return true;
        for (int v: adj[u]) {
            if (dist[pairV[v]] == dist[u] + 1 && dfs(pairV[v])) {
                pairU[u] = v;
                pairV[v] = u;
                return true;
            }
        }
        dist[u] = INF;
        return false;
    }

    int maxMatching() {
        int result = 0;
        while (bfs()) {
            FOR(u,1,nL) {
                if (pairU[u] == 0 && dfs(u))
                    ++result;
            }
        }
        return result;
    }
};

int n, m;
vector<string> grid;

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    grid.resize(n);
    FOR(i,0,n-1) {
        cin >> grid[i];
    }

    // Đánh dấu các đoạn chạy # theo hàng (horizontal runs)
    vector<vector<int>> h_id(n, vector<int>(m, 0));
    int cntH = 0;
    FOR(i,0,n-1) {
        FOR(j,0,m-1) {
            if (grid[i][j] == '#') {
                if (j == 0 || grid[i][j-1] == '.') {
                    ++cntH;
                }
                h_id[i][j] = cntH;
            }
        }
    }

    // Đánh dấu các đoạn chạy # theo cột (vertical runs)
    vector<vector<int>> v_id(n, vector<int>(m, 0));
    int cntV = 0;
    FOR(j,0,m-1) {
        FOR(i,0,n-1) {
            if (grid[i][j] == '#') {
                if (i == 0 || grid[i-1][j] == '.') {
                    ++cntV;
                }
                v_id[i][j] = cntV;
            }
        }
    }

    // Xây dựng đồ thị song phân: H (1..cntH) – V (1..cntV)
    HopcroftKarp hk(cntH, cntV);
    FOR(i,0,n-1) FOR(j,0,m-1) {
        if (grid[i][j] == '#') {
            hk.addEdge(h_id[i][j], v_id[i][j]);
        }
    }

    // Kết quả = size của maximum matching = size của minimum vertex cover
    cout << hk.maxMatching() << "\n";
}

int main() {
    solve();
    return 0;
}

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