Submission #1257641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257641		hptcqt	Selotejp (COCI20_selotejp)	C++20	110 / 110	2 ms	1096 KiB

Main

#include<bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;
int m, n, a[1005][15], hang[1005][15], cot[1005][15], M, N, mat[10005], dem = 0, tmp = 0;
int pairU[10005], pairV[10005], dist[10005];
bool d[10005], mark[10005][10005]; vector<int> adj[10005];
bool bfs() {
    queue<int> q;
    for (int u = 1; u <= M; u++) {
        if (pairU[u] == 0) {
            dist[u] = 0;
            q.push(u);
        } else dist[u] = 1e9 + 7;
    }
    dist[0] = 1e9 + 7;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (dist[u] < dist[0]) {
            for (int v : adj[u]) {
                if (dist[pairV[v]] == 1e9 + 7) {
                    dist[pairV[v]] = dist[u] + 1;
                    q.push(pairV[v]);
                }
            }
        }
    }
    return dist[0] != 1e9 + 7;
}
bool dfs(int u) {
    if (u != 0) {
        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] = 1e9 + 7;
        return false;
    }
    return true;
}
int hopcroftKarp() {
    memset(pairU, 0, sizeof(pairU));
    memset(pairV, 0, sizeof(pairV));
    int result = 0;
    while (bfs()) {
        for (int u = 1; u <= M; u++) {
            if (pairU[u] == 0 && dfs(u)) {
                result++;
            }
        }
    }
    return result;
}
signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) {
        char c; cin >> c;
        a[i][j] = (c == '.'); tmp += !a[i][j];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j < n; j++) {
            if (!a[i][j] && !a[i][j + 1]) {
                hang[i][j] = ++M;
            }
        }
    }
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i < m; i++)
            if (!a[i][j] && !a[i + 1][j]) {
                cot[i][j] = ++N;
            }
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (i < m && j < n && hang[i][j] && cot[i][j])
                adj[hang[i][j]].push_back(cot[i][j]);
            if (j < n && i > 1 && hang[i][j] && cot[i - 1][j])
                adj[hang[i][j]].push_back(cot[i - 1][j]);
            if (j > 1 && i > 1 && hang[i][j - 1] && cot[i - 1][j])
                adj[hang[i][j - 1]].push_back(cot[i - 1][j]);
            if (i < m && j > 1 && hang[i][j - 1] && cot[i][j])
                adj[hang[i][j - 1]].push_back(cot[i][j]);
        }
    cout << tmp - (M + N - hopcroftKarp());
}

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