Submission #1247944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247944		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 ALL(x) (x).begin(), (x).end()
#define endl "\n"

const int MAXNM = 1000*10 + 5;  // tối đa n*m
const int INF = 1e9;

int n, m;
vector<string> a;

// ---- Hopcroft-Karp để tìm max matching trên bipartite graph (U size = Hn, V size = Vn) ----
int Hn, Vn;                       // số nút bên trái (H) và bên phải (V)
vector<vector<int>> adj;          // adj[u] = danh sách v bên phải
vector<int> distHK, pairU, pairV;

bool bfsHK(){
    queue<int> q;
    distHK.assign(Hn+1, INF);
    FOR(u,1,Hn){
        if(pairU[u]==0){
            distHK[u] = 0;
            q.push(u);
        }
    }
    bool reachableFreeV = false;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: adj[u]){
            int pu = pairV[v];
            if(pu==0){
                // tìm được đường tăng
                reachableFreeV = true;
            } else if(distHK[pu]==INF){
                distHK[pu] = distHK[u] + 1;
                q.push(pu);
            }
        }
    }
    return reachableFreeV;
}

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

int hopcroftKarp(){
    pairU.assign(Hn+1, 0);
    pairV.assign(Vn+1, 0);
    distHK.assign(Hn+1, INF);
    int matching = 0;
    while(bfsHK()){
        FOR(u,1,Hn){
            if(pairU[u]==0 && dfsHK(u))
                matching++;
        }
    }
    return matching;
}
// ----------------------------------------------------------------------------

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

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

    // 1) đánh số phân đoạn ngang
    vector<vector<int>> h_id(n, vector<int>(m, 0));
    Hn = 0;
    FOR(i,0,n-1){
        int cur = 0;
        FOR(j,0,m-1){
            if(a[i][j]=='#'){
                if(j==0 || a[i][j-1]=='.'){
                    ++Hn;
                }
                h_id[i][j] = Hn;
            }
        }
    }

    // 2) đánh số phân đoạn dọc
    vector<vector<int>> v_id(n, vector<int>(m, 0));
    Vn = 0;
    FOR(j,0,m-1){
        FOR(i,0,n-1){
            if(a[i][j]=='#'){
                if(i==0 || a[i-1][j]=='.'){
                    ++Vn;
                }
                v_id[i][j] = Vn;
            }
        }
    }

    // 3) build bipartite graph
    adj.assign(Hn+1, {});
    FOR(i,0,n-1) FOR(j,0,m-1){
        if(a[i][j]=='#'){
            int u = h_id[i][j];
            int v = v_id[i][j];
            adj[u].push_back(v);
        }
    }

    // 4) max matching = min tape segments
    int ans = hopcroftKarp();
    cout << ans << endl;
    return 0;
}

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