Submission #2022455
Source Code Expand
#include<stack>
#include<queue>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
putchar('\n');
}
struct Dinic {
typedef int Flow;
static const Flow INF = 1<<29;
struct Edge {
int src, dst;
Flow cap;
int rev;
};
typedef vector<vector<Edge> > Graph;
Graph G;
vector<int>len, iter;
Dinic(int N) : G(N) {}
void add_edge(int u, int v, Flow c) {
G[u].push_back((Edge){ u, v, c, (int)G[v].size() });
G[v].push_back((Edge){ v, u, 0, (int)G[u].size()-1 });
}
Flow dfs(int v, int s, Flow c) {
if (v == s || c == 0) return c;
Flow ret = 0;
for (int &i=iter[v]; i<(int)G[v].size(); i++) {
Edge &e = G[v][i], &re = G[e.dst][e.rev];
if (re.cap > 0 && len[v] > len[e.dst]) {
Flow f = dfs(e.dst, s, min(c-ret, re.cap));
ret += f;
e.cap += f; re.cap -= f;
if (ret == c) break;
}
}
return ret;
}
void bfs(int s) {
len.assign(G.size(), -1);
queue<int>qu;
qu.push(s);
len[s] = 0;
for (;!qu.empty();) {
int v = qu.front(); qu.pop();
for (int i=0; i<(int)G[v].size(); i++) {
const Edge &e = G[v][i];
if (e.cap > 0 && len[e.dst] == -1) {
len[e.dst] = len[v] + 1;
qu.push(e.dst);
}
}
}
}
Flow _flow;
Flow flow(int source, int sink, Flow limit=-1) {
if (limit == -1) limit = INF;
Flow ret = 0;
while (true) {
bfs(source);
if (len[sink] == -1 || limit == 0) return _flow = ret;
iter.assign(G.size(), 0);
Flow tmp = dfs(sink, source, limit);
ret += tmp;
limit -= tmp;
}
}
};
const Dinic::Flow Dinic::INF;
int R, C;
char F[55][55];
void MAIN() {
scanf("%d%d", &R, &C);
REP (i, R) scanf("%s", F[i]);
if (C % 2 == 0) {
REP (i, R) F[i][C] = '*';
C++;
}
int SRC = R*C, SNK = SRC + 1;
Dinic D(SNK+1);
int cnt = 0;
REP (i, R) REP (j, C) {
if (F[i][j] == '.') {
cnt++;
int v = i * C + j;
if (v & 1) {
D.add_edge(v, SNK, 1);
} else {
D.add_edge(SRC, v, 1);
}
if (i+1 < R && F[i+1][j] == '.') {
int a = v, b = v+C;
if (a & 1) swap(a, b);
D.add_edge(a, b, 1);
}
if (j+1 < C && F[i][j+1] == '.') {
int a = v, b = v+1;
if (a & 1) swap(a, b);
D.add_edge(a, b, 1);
}
}
}
int f = D.flow(SRC, SNK);
// eprintf("%d %d\n", cnt, f);
printf("%d\n", cnt - f);
}
int main() {
int TC = 1;
// scanf("%d", &TC);
REP (tc, TC) MAIN();
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 広告 |
User |
natsugiri |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3190 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
384 KB |
Compile Error
./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:90:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &R, &C);
^
./Main.cpp:91:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP (i, R) scanf("%s", F[i]);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
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 |
1 ms |
256 KB |
01-01.txt |
AC |
2 ms |
384 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
1 ms |
384 KB |
01-04.txt |
AC |
2 ms |
384 KB |
01-05.txt |
AC |
2 ms |
384 KB |
01-06.txt |
AC |
2 ms |
384 KB |
01-07.txt |
AC |
1 ms |
256 KB |
01-08.txt |
AC |
2 ms |
384 KB |
01-09.txt |
AC |
2 ms |
384 KB |
01-10.txt |
AC |
2 ms |
384 KB |
01-11.txt |
AC |
1 ms |
256 KB |
01-12.txt |
AC |
2 ms |
384 KB |
01-13.txt |
AC |
2 ms |
384 KB |
01-14.txt |
AC |
1 ms |
384 KB |
01-15.txt |
AC |
2 ms |
384 KB |
01-16.txt |
AC |
1 ms |
256 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 |