Submission #2180949
Source Code Expand
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct Dinic {
#define MAX_V 30000
struct Edge { int to, cap, rev; };
vector<Edge> G[MAX_V];
int level[MAX_V], iter[MAX_V];
void add_edge(int x, int y, int cap) {
G[x].pb({ y, cap, (int)G[y].size() });
G[y].pb({ x, 0, (int)G[x].size()-1 });
}
void bfs(int s) {
rep(i, MAX_V) level[i] = INF;
queue<int> q;
q.push(s);
level[s] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (Edge e : G[x]) {
if (e.cap > 0 && level[e.to] == INF) {
level[e.to] = level[x]+1;
q.push(e.to);
}
}
}
}
int dfs(int x, int goal, int f) {
if (x == goal) return f;
for (int &i=iter[x]; i<G[x].size(); i++) {
Edge &e = G[x][i];
if (e.cap > 0 && level[x] < level[e.to]) {
int w = dfs(e.to, goal, min(f, e.cap));
if (w > 0) {
e.cap -= w;
G[e.to][e.rev].cap += w;
return w;
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
while (true) {
bfs(s);
if (level[t] == INF) return flow;
rep(i, MAX_V) iter[i] = 0;
while (true) {
int f = dfs(s, t, INF);
if (f == 0) break;
flow += f;
}
}
}
};
Dinic dinic;
int H, W;
char A[100][100];
int IN[100][100], OUT[100][100];
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> H >> W;
int V = 0;
rep(y, H) {
rep(x, W) {
cin >> A[x][y];
if (A[x][y] == 'X') {
IN[x][y] = OUT[x][y] = V++;
}
else {
IN[x][y] = V++;
OUT[x][y] = V++;
dinic.add_edge(IN[x][y], OUT[x][y], 1);
}
}
}
int s = V++, t = V++;
rep(x, W) rep(y, H) {
if (A[x][y] == 'X') dinic.add_edge(s, IN[x][y], INF);
}
rep(x, W) rep(y, H) if (x == 0 || x == W-1 || y == 0 || y == H-1) {
if (A[x][y] == 'X') {
cout << -1 << "\n";
return 0;
}
dinic.add_edge(OUT[x][y], t, INF);
}
rep(x, W-1) rep(y, H) dinic.add_edge(OUT[x][y], IN[x+1][y], INF), dinic.add_edge(OUT[x+1][y], IN[x][y], INF);
rep(x, W) rep(y, H-1) dinic.add_edge(OUT[x][y], IN[x][y+1], INF), dinic.add_edge(OUT[x][y+1], IN[x][y], INF);
cout << dinic.max_flow(s, t) << "\n";
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
funcsr |
Language |
C++14 (GCC 5.4.1) |
Score |
150 |
Code Size |
2928 Byte |
Status |
AC |
Exec Time |
50 ms |
Memory |
3456 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 |
2 ms |
1280 KB |
01_sample.txt |
AC |
2 ms |
1024 KB |
02_sample.txt |
AC |
2 ms |
1280 KB |
10_rand_00.txt |
AC |
2 ms |
1280 KB |
10_rand_01.txt |
AC |
3 ms |
1408 KB |
10_rand_02.txt |
AC |
14 ms |
2048 KB |
10_rand_03.txt |
AC |
16 ms |
1920 KB |
10_rand_04.txt |
AC |
8 ms |
3328 KB |
10_rand_05.txt |
AC |
15 ms |
3456 KB |
10_rand_06.txt |
AC |
8 ms |
1920 KB |
10_rand_07.txt |
AC |
15 ms |
2688 KB |
10_rand_08.txt |
AC |
29 ms |
3328 KB |
11_hashi_00.txt |
AC |
2 ms |
1280 KB |
11_hashi_01.txt |
AC |
2 ms |
1152 KB |
11_hashi_02.txt |
AC |
2 ms |
1408 KB |
12_rect_00.txt |
AC |
50 ms |
3072 KB |
12_rect_01.txt |
AC |
8 ms |
1792 KB |
12_rect_02.txt |
AC |
9 ms |
2816 KB |
99_all_one.txt |
AC |
2 ms |
1536 KB |