Submission #2025646


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<class V> struct MaxFlow { // Dinic O(V^2E)
    struct edge { int to, reve; V cap; edge(int t, int r, V c) : to(t), reve(r), cap(c) {} };
    int MV; vector<vector<edge>> E; vector<int> itr, lev;
    MaxFlow(int n) { init(n); } MaxFlow() { }
    void init(int n){MV=n;itr=vector<int>(MV),lev = vector<int>(MV); E = vector<vector<edge>>(MV); }
    void add_edge(int x, int y, V cap, bool undir = false) {
        E[x].push_back(edge(y, (int)E[y].size(), cap));
        E[y].push_back(edge(x, (int)E[x].size() - 1, undir ? cap : 0));}
    void bfs(int cur) {rep(i, 0, MV) lev[i] = -1; queue<int> q; lev[cur] = 0; q.push(cur);
        while (q.size()) {int v = q.front(); q.pop();
        for (auto e : E[v]) if (e.cap>0 && lev[e.to]<0) lev[e.to] = lev[v] + 1, q.push(e.to);}}
    V dfs(int from,int to,V cf){if(from==to)return cf;for(; itr[from]<E[from].size(); itr[from]++) {
        edge* e = &E[from][itr[from]]; if (e->cap>0 && lev[from]<lev[e->to]) {
        V f = dfs(e->to, to, min(cf, e->cap));if(f>0){e->cap-=f;E[e->to][e->reve].cap+=f;return f; }}
        } return 0;}
    V maxflow(int from, int to) {V fl = 0, tf;while (1) {bfs(from); if (lev[to]<0) return fl;
        rep(i,0,MV)itr[i]=0; while ((tf = dfs(from, to, numeric_limits<V>::max()))>0) fl += tf;}}};
struct BipartiteMatching {
    int N, M; MaxFlow<int> mf;
    BipartiteMatching(int n, int m) : N(n), M(m) { mf.init(n + m + 2); }
    void add_edge(int a, int b) { mf.add_edge(a, N + b, 1); }
    int match() { rep(a, 0, N) mf.add_edge(N + M, a, 1); rep(b, 0, M) mf.add_edge(N + b, N + M + 1, 1);
        return mf.maxflow(N + M, N + M + 1); }
    // マッチング相手を返す(無いなら-1)
    int whois(int a) { for (auto e : mf.E[a]) if (e.cap == 0) return e.to - N; return -1; }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/




int H, W;
string C[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> C[y];

    int N = H * W;
    BipartiteMatching bm(N, N);
    rep(y, 0, H) rep(x, 0, W) {
        if ((y + x) % 2 == 0) {
            if(x < W - 1) if (C[y][x] == '.' and C[y][x + 1] == '.') bm.add_edge(y * W + x, y * W + x + 1);
            if(y < H - 1) if (C[y][x] == '.' and C[y + 1][x] == '.') bm.add_edge(y * W + x, (y + 1) * W + x);
        }
        else {
            if (x < W - 1) if (C[y][x] == '.' and C[y][x + 1] == '.') bm.add_edge(y * W + x + 1, y * W + x);
            if (y < H - 1) if (C[y][x] == '.' and C[y + 1][x] == '.') bm.add_edge((y + 1) * W + x, y * W + x);
        }
    }

    int ans = -bm.match();
    rep(y, 0, H) rep(x, 0, W) if (C[y][x] == '.') ans++;
    cout << ans << endl;
}

Submission Info

Submission Time
Task C - 広告
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3965 Byte
Status AC
Exec Time 2 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 4
AC × 21
Set Name Test Cases
Sample sample0.txt, sample1.txt, sample2.txt, sample3.txt
All 01-00.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
01-00.txt AC 2 ms 512 KB
01-01.txt AC 2 ms 512 KB
01-02.txt AC 1 ms 512 KB
01-03.txt AC 2 ms 512 KB
01-04.txt AC 2 ms 512 KB
01-05.txt AC 2 ms 512 KB
01-06.txt AC 2 ms 512 KB
01-07.txt AC 2 ms 512 KB
01-08.txt AC 2 ms 512 KB
01-09.txt AC 2 ms 512 KB
01-10.txt AC 2 ms 512 KB
01-11.txt AC 2 ms 512 KB
01-12.txt AC 2 ms 512 KB
01-13.txt AC 2 ms 512 KB
01-14.txt AC 2 ms 512 KB
01-15.txt AC 2 ms 512 KB
01-16.txt AC 1 ms 512 KB
sample0.txt AC 1 ms 256 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB