Submission #10578369
Source Code Expand
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;
template <typename T> class Dinic {
struct edge {
int to, rev;
T cap;
bool isrev;
edge(int t, T c, int r, bool i) : to(t), cap(c), rev(r), isrev(i) {}
};
void bfs(int s, int t) {
lev.assign(g.size(), -1);
queue<int> que;
lev[s] = 0;
que.emplace(s);
while (!que.empty() && lev[t] == -1) {
int v = que.front();
que.pop();
for (edge& e : g[v]) {
if (lev[e.to] == -1 && e.cap > 0) {
lev[e.to] = lev[v] + 1;
que.emplace(e.to);
}
}
}
}
T dfs(int v, int t, T f) {
if (v == t) return f;
for (int& i = ite[v]; i < g[v].size(); ++i) {
edge& e = g[v][i];
if (e.cap > 0 && lev[v] < lev[e.to]) {
T d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
public:
const T INF;
vector<int> lev, ite;
vector<vector<edge>> g;
Dinic(int n) : INF(numeric_limits<T>::max()), g(n) {}
void add_edge(int f, int t, T c = numeric_limits<T>::max()) {
g[f].emplace_back(t, c, g[t].size(), false);
g[t].emplace_back(f, 0, g[f].size() - 1, true);
}
T max_flow(int s, int t) {
T res = 0;
while (1) {
bfs(s, t);
if (lev[t] < 0) break;
ite.assign(g.size(), 0);
T f = 0;
while ((f = dfs(s, t, INF)) > 0) {
res += f;
}
}
return res;
}
void print() {
for (int i = 0; i < g.size(); ++i) {
for (auto& e : g[i]) {
if (e.isrev) continue;
auto& rev_e = g[e.to][e.rev];
cout << i << " -> " << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
}
}
}
};
const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};
int H, W;
string S[100];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> H >> W;
REP (i, H) cin >> S[i];
REP (i, H) if (S[i][0] == 'X' || S[i][W - 1] == 'X') {
cout << -1 << endl;
return 0;
}
REP (j, W) if (S[0][j] == 'X' || S[H - 1][j] == 'X') {
cout << -1 << endl;
return 0;
}
Dinic<int> g(2 * H * W + 2);
int s = 2 * H * W, t = s + 1;
REP (i, H) REP (j, W) {
if (S[i][j] == 'X') {
g.add_edge(s, 2 * (i * W + j) + 1);
g.add_edge(2 * (i * W + j), 2 * (i * W + j) + 1);
} else {
g.add_edge(2 * (i * W + j), 2 * (i * W + j) + 1, 1);
}
REP (k, 4) {
int ny = i + dy[k];
int nx = j + dx[k];
if (ny >= 0 && ny < H && nx >= 0 && nx < W) {
g.add_edge(2 * (i * W + j) + 1, 2 * (ny * W + nx));
}
}
}
REP (i, H) {
g.add_edge(2 * (i * W) + 1, t);
g.add_edge(2 * (i * W + W - 1) + 1, t);
}
REP (j, W) {
g.add_edge(2 * j + 1, t);
g.add_edge(2 * ((H - 1) * W + j) + 1, t);
}
cout << g.max_flow(s, t) << endl;
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
legosuke |
Language |
C++14 (GCC 5.4.1) |
Score |
150 |
Code Size |
3622 Byte |
Status |
AC |
Exec Time |
38 ms |
Memory |
6144 KB |
Judge Result
Set Name |
All |
Score / Max Score |
150 / 150 |
Status |
|
Set Name |
Test Cases |
All |
00_sample.txt, 01_sample.txt, 02_sample.txt, 10_rand_00.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 11_hashi_00.txt, 11_hashi_01.txt, 11_hashi_02.txt, 12_rect_00.txt, 12_rect_01.txt, 12_rect_02.txt, 99_all_one.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample.txt |
AC |
1 ms |
256 KB |
01_sample.txt |
AC |
1 ms |
256 KB |
02_sample.txt |
AC |
1 ms |
256 KB |
10_rand_00.txt |
AC |
1 ms |
384 KB |
10_rand_01.txt |
AC |
2 ms |
512 KB |
10_rand_02.txt |
AC |
11 ms |
2304 KB |
10_rand_03.txt |
AC |
12 ms |
2048 KB |
10_rand_04.txt |
AC |
9 ms |
5888 KB |
10_rand_05.txt |
AC |
16 ms |
6144 KB |
10_rand_06.txt |
AC |
4 ms |
2176 KB |
10_rand_07.txt |
AC |
13 ms |
3968 KB |
10_rand_08.txt |
AC |
27 ms |
5504 KB |
11_hashi_00.txt |
AC |
1 ms |
256 KB |
11_hashi_01.txt |
AC |
1 ms |
256 KB |
11_hashi_02.txt |
AC |
1 ms |
256 KB |
12_rect_00.txt |
AC |
38 ms |
5248 KB |
12_rect_01.txt |
AC |
6 ms |
1536 KB |
12_rect_02.txt |
AC |
10 ms |
4604 KB |
99_all_one.txt |
AC |
1 ms |
256 KB |