Submission #1247942

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

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m;
vector<string> a;

// Đánh số các segment ngang và dọc
vector<vector<int>> hID, vID;
int hCnt = 0, vCnt = 0;

// Đồ thị bipartite: từ 1..hCnt sang 1..vCnt
vector<vector<int>> adj;  
vector<int> matchR;
vector<char> seen;

// DFS tìm augmenting path từ u bên trái
bool tryKuhn(int u){
    for(int v: adj[u]){
        if(seen[v]) continue;
        seen[v] = 1;
        // nếu v chưa ghép hoặc có thể đẩy tiếp path
        if(matchR[v]==0 || tryKuhn(matchR[v])){
            matchR[v] = u;
            return true;
        }
    }
    return false;
}

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

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

    hID.assign(n, vector<int>(m,0));
    vID.assign(n, vector<int>(m,0));

    // 1) đánh số ngang
    for(int i=0;i<n;i++){
        int cur = 0;
        for(int j=0;j<m;j++){
            if(a[i][j]=='#'){
                if(cur==0) cur = ++hCnt;
                hID[i][j] = cur;
            } else {
                cur = 0;
            }
        }
    }
    // 2) đánh số dọc
    for(int j=0;j<m;j++){
        int cur = 0;
        for(int i=0;i<n;i++){
            if(a[i][j]=='#'){
                if(cur==0) cur = ++vCnt;
                vID[i][j] = cur;
            } else {
                cur = 0;
            }
        }
    }

    // 3) xây đồ thị
    adj.assign(hCnt+1, {});
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]=='#'){
                adj[hID[i][j]].push_back(vID[i][j]);
            }
        }
    }

    // 4) matchR[v] = u nghĩa v (phía phải) ghép với u (phía trái)
    matchR.assign(vCnt+1, 0);
    int matching = 0;

    // với mỗi u bên trái, thử DFS tìm augmenting path
    for(int u=1; u<=hCnt; u++){
        seen.assign(vCnt+1, 0);
        if(tryKuhn(u)) matching++;
    }

    // matching = kích thước max-matching = min-vertex-cover
    cout << matching << "\n";
    return 0;
}

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