Submission #4578400


Source Code Expand

Copy
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<fstream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

// 最大流
struct Edge{
    ll to;
    ll capacity;
    ll rev; // index
    Edge(ll t, ll c, ll r){
        to = t;
        capacity = c;
        rev = r;
    }
    Edge(){}
};

// ford fulkerson ver
struct MaxFlow{
    vector<vector<Edge> > G;
    vector<bool> used;

    MaxFlow(ll node_num){
        G.resize(node_num);
        used.resize(node_num);
    }

    void add_edge(ll from, ll to, ll capacity){
        G[from].push_back(Edge(to, capacity, G[to].size()));
        G[to].push_back(Edge(from, 0, G[from].size()-1));
    }

    ll dfs(ll v, ll t, ll flow){
        if(v==t) return flow;
        used[v] = true;
        for(Edge &edge : G[v]){
            if(!used[edge.to] && edge.capacity > 0){
                ll d = dfs(edge.to, t, min(flow, edge.capacity));
                if(d>0){
                    edge.capacity -= d;
                    G[edge.to][edge.rev].capacity += d;
                    return d;
                }
            }
        }
        return 0;
    }

    ll calc(ll start, ll end){
        ll flow_sum = 0;
        while(true){
            fill(ALL(used), false);
            ll f = dfs(start, end, inf);
            if(f==0){
                break;
            }
            flow_sum += f;
        }
        return flow_sum;
    }
};

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

ll R, C;
ll id(ll i, ll j){
    return C*i + j;
}

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

    // input
    cin >> R >> C;
    ll N = R*C;
    
    vector<string> S(R);
    FOR(i, 0, R){
        cin >> S[i];
    }

    auto mf = MaxFlow(N+2);
    // N : 始点
    // N+1: 終点とする

    // (0,0) : black
    // (0,1) : white
    // とし、二部グラフで s -> blacks -> whites -> t と流す
    
    FOR(i, 0, R){
        FOR(j, 0, C){
            if(S[i][j]=='*') continue;
            ll index = id(i, j);
            
            if((i+j)%2==0){
                FOR(k, 0, 4){
                    ll ny = i + dy[k];
                    ll nx = j + dx[k];

                    if(0<=ny && ny<R && 0<=nx && nx<C && S[ny][nx]=='.'){
                        ll from = id(i, j);
                        ll to = id(ny, nx);
                        mf.add_edge(from, to, 1);
                    }
                }
            }

            // 始点・終点からも引く
            if((i+j)%2==0){
                mf.add_edge(N, index, 1);
            }
            else{
                mf.add_edge(index, N+1, 1);
            }
        }
    }

    ll max_flow = mf.calc(N, N+1);
    
    ll count = 0;
    FOR(i, 0, R){
        for(char c : S[i]){
            if(c=='.'){
                count++;
            }
        }
    }

    p(count - max_flow);

    return 0;
}

Submission Info

Submission Time
Task C - 広告
User peroon
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3386 Byte
Status
Exec Time 4 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
× 4
× 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 1 ms 256 KB
01-01.txt 3 ms 512 KB
01-02.txt 1 ms 256 KB
01-03.txt 2 ms 384 KB
01-04.txt 4 ms 512 KB
01-05.txt 2 ms 384 KB
01-06.txt 4 ms 512 KB
01-07.txt 1 ms 256 KB
01-08.txt 3 ms 512 KB
01-09.txt 4 ms 512 KB
01-10.txt 3 ms 384 KB
01-11.txt 1 ms 256 KB
01-12.txt 3 ms 512 KB
01-13.txt 3 ms 512 KB
01-14.txt 2 ms 384 KB
01-15.txt 3 ms 512 KB
01-16.txt 1 ms 256 KB
sample0.txt 1 ms 256 KB
sample1.txt 1 ms 256 KB
sample2.txt 1 ms 256 KB
sample3.txt 1 ms 256 KB