제출 #1257639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257639		hptcqt	Selotejp (COCI20_selotejp)	C++20	70 / 110	1095 ms	40628 KiB

Main

#pragma GCC optimize("Ofast")
#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;
bool d[10005], mark[10005][10005];
bool ghep (int i) {
    if (d[i]) return false;
    d[i] = 1;
    for (int j = 1; j <= N; j++) {
        if (mark[i][j])
            if (!mat[j] || ghep(mat[j])) {
                mat[j] = i;
                return true;
            }
    }
    return false;
}
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]) {
                mark[hang[i][j]][cot[i][j]] = 1;
            }
            if (j < n && i > 1 && hang[i][j] && cot[i - 1][j]) {
                mark[hang[i][j]][cot[i - 1][j]] = 1;
            }
            if (j > 1 && i > 1 && hang[i][j - 1] && cot[i - 1][j]) {
                mark[hang[i][j - 1]][cot[i - 1][j]] = 1;
            }
            if (i < m && j > 1 && hang[i][j - 1] && cot[i][j]) {
                mark[hang[i][j - 1]][cot[i][j]] = 1;
            }
        }
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) d[j] = 0;
        dem += ghep(i);
    }
    cout << tmp - (M + N - dem);
}

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