Submission #1247940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247940		dfhdfhdsf	Selotejp (COCI20_selotejp)	C++20	35 / 110	1 ms	584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;

struct HopcroftKarp {
    int nL, nR;
    vector<vector<int>> adj;
    vector<int> dist, pairU, pairV;

    HopcroftKarp(int _nL, int _nR): nL(_nL), nR(_nR) {
        adj.assign(nL + 1, {});
        pairU.assign(nL + 1, 0);
        pairV.assign(nR + 1, 0);
        dist.assign(nL + 1, 0);
    }

    void addEdge(int u, int v) {
        // u in [1..nL], v in [1..nR]
        adj[u].push_back(v);
    }

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

    bool dfs(int u) {
        for (int v : adj[u]) {
            if (pairV[v] == 0 || (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 (int u = 1; u <= nL; u++) {
                if (pairU[u] == 0 && dfs(u)) {
                    result++;
                }
            }
        }
        return result;
    }
};

int n, m;
vector<string> a;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    a.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    // 1) Đánh số segment ngang
    vector<vector<int>> hID(n, vector<int>(m, 0));
    int hCount = 0;
    for(int i = 0; i < n; i++){
        int curr = 0;
        for(int j = 0; j < m; j++){
            if(a[i][j] == '#'){
                if(curr == 0){
                    curr = ++hCount;
                }
                hID[i][j] = curr;
            } else {
                curr = 0;
            }
        }
    }

    // 2) Đánh số segment dọc
    vector<vector<int>> vID(n, vector<int>(m, 0));
    int vCount = 0;
    for(int j = 0; j < m; j++){
        int curr = 0;
        for(int i = 0; i < n; i++){
            if(a[i][j] == '#'){
                if(curr == 0){
                    curr = ++vCount;
                }
                vID[i][j] = curr;
            } else {
                curr = 0;
            }
        }
    }

    // 3) Xây đồ thị bipartite
    HopcroftKarp hk(hCount, vCount);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == '#'){
                int u = hID[i][j];
                int v = vID[i][j];
                hk.addEdge(u, v);
            }
        }
    }

    // 4) Kết quả = max matching = min vertex cover
    cout << hk.maxMatching() << "\n";
    return 0;
}

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