Contest Duration: ~ (local time)

Submission #2161432

Source Code Expand

Copy
```#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

struct Bipartite_Matching
{
vector< vector< int > > graph;
vector< int > match, alive, used;
int timestamp;

Bipartite_Matching(int n)
{
timestamp = 0;
graph.resize(n);
alive.assign(n, 1);
used.assign(n, 0);
match.assign(n, -1);
}

{
graph[u].push_back(v);
graph[v].push_back(u);
}

bool dfs(int v)
{
used[v] = timestamp;
for(int i = 0; i < graph[v].size(); i++) {
int u = graph[v][i], w = match[u];
if(alive[u] == 0) continue;
if(w == -1 || (used[w] != timestamp && dfs(w))) {
match[v] = u;
match[u] = v;
return (true);
}
}
return (false);
}

int bipartite_matching()
{
int ret = 0;
for(int i = 0; i < graph.size(); i++) {
if(alive[i] == 0) continue;
if(match[i] == -1) {
++timestamp;
ret += dfs(i);
}
}
return (ret);
}
};

int main(){
int i,j;
int r,c;
cin>>r>>c;
vs s(r);
rep(i,r)cin>>s[i];
int sum=0;
rep(i,r)rep(j,c)if(s[i][j]=='.')sum++;

Bipartite_Matching flow(r*c);

rep(i,r)rep(j,c)if(s[i][j]=='.'){
if(i>0 && s[i-1][j]=='.')
if(j>0 && s[i][j-1]=='.')
}

cout << sum - flow.bipartite_matching() << endl;

}

```

Submission Info

Submission Time 2018-03-05 01:14:49+0900 C - 広告 rika0384 C++14 (GCC 5.4.1) 400 2080 Byte AC 2 ms 384 KB

Test Cases

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