Submission #1246021
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()
#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second
#define x1 gray_cat_x1
#define y1 gray_cat_y1
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
#define file "cycle"
const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e4;
const ll MOD = 1e9 + 7;
const int MAXN = 2e4 + 5;
struct edge{
int s, to, cap, flow;
};
struct graph {
// Number of vertices and edges
int n;
// Edges
vector<edge> ee;
// Graph
vi g[MAXN];
// start, finish
int s, t;
// Distance for BFS
int dis[MAXN];
// Queue for BFS
int qq[MAXN];
// Ptr for DFS
int ptr[MAXN];
// Adding edge
void add_edge(int a, int b, int cap){
edge e1 = { a, b, cap, 0 };
edge e2 = { b, a, 0, 0 };
g[a].pb(SZ(ee));
ee.pb(e1);
g[b].pb(SZ(ee));
ee.pb(e2);
}
// BFS for Dinic
bool bfs(){
// Init
int qh = 0, qt = 0;
qq[qt++] = s;
REPN(i, 1, n){
dis[i] = -1;
}
dis[s] = 0;
// Go
while (qh < qt) {
int v = qq[qh++];
REP(i, 0, SZ(g[v])){
int ind = g[v][i];
int to = ee[ind].to;
if (dis[to] == -1 && ee[ind].flow < ee[ind].cap) {
qq[qt++] = to;
dis[to] = dis[v] + 1;
}
}
}
return dis[t] != -1;
}
// DFS for Dinic
int dfs (int v, int cur_flow){
if (!cur_flow){
return 0;
}
if (v == t) {
return cur_flow;
}
for (; ptr[v] < SZ(g[v]); ++ptr[v]) {
int ind = g[v][ptr[v]];
int to = ee[ind].to;
if (dis[to] != dis[v] + 1) {
continue;
}
int pushed = dfs(to, min(cur_flow, ee[ind].cap - ee[ind].flow));
if (pushed) {
ee[ind].flow += pushed;
ee[ind ^ 1].flow -= pushed;
return pushed;
}
}
return 0;
}
// Dinic
int dinic(int _s, int _t) {
// Init
s = _s, t = _t;
REP(i, 0, SZ(ee)){
ee[i].flow = 0;
}
int result = 0;
// Go
while(1) {
if (!bfs()) {
break;
}
REPN(i, 1, n){
ptr[i] = 0;
}
while (int pushed = dfs(s, INF)) {
result += pushed;
}
}
return result;
}
};
graph gg;
char c[200][200];
int in[200][200], out[200][200];
void solve(){
int n, m;
scanf("%d%d", &n, &m);
REP(i, 0, n){
scanf("%s", &c[i][0]);
}
gg.n = 2 * n * m + 2;
int s = gg.n - 1, f = gg.n;
REP(i, 0, n){
REP(j, 0, m){
in[i][j] = i * m + j + 1;
out[i][j] = in[i][j] + n * m;
}
}
REP(i, 0, n){
REP(j, 0, m){
gg.add_edge(in[i][j], out[i][j], 1);
if (i > 0){
gg.add_edge(out[i][j], in[i - 1][j], INF);
} else {
gg.add_edge(out[i][j], f, INF);
}
if (i < n - 1){
gg.add_edge(out[i][j], in[i + 1][j], INF);
} else {
gg.add_edge(out[i][j], f, INF);
}
if (j > 0){
gg.add_edge(out[i][j], in[i][j - 1], INF);
} else {
gg.add_edge(out[i][j], f, INF);
}
if (j < m - 1){
gg.add_edge(out[i][j], in[i][j + 1], INF);
} else {
gg.add_edge(out[i][j], f, INF);
}
if (c[i][j] == 'X'){
gg.add_edge(s, out[i][j], INF);
}
}
}
int ans = gg.dinic(s, f);
if (ans >= INF){
ans = -1;
}
printf("%d\n", ans);
}
int main(){
//freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
Timur_Sitdikov |
Language |
C++14 (GCC 5.4.1) |
Score |
150 |
Code Size |
3840 Byte |
Status |
AC |
Exec Time |
60 ms |
Memory |
3952 KB |
Compile Error
./Main.cpp: In function ‘void solve()’:
./Main.cpp:156:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:158:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &c[i][0]);
^
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 |
768 KB |
01_sample.txt |
AC |
2 ms |
768 KB |
02_sample.txt |
AC |
2 ms |
768 KB |
10_rand_00.txt |
AC |
2 ms |
768 KB |
10_rand_01.txt |
AC |
2 ms |
896 KB |
10_rand_02.txt |
AC |
15 ms |
1784 KB |
10_rand_03.txt |
AC |
17 ms |
1656 KB |
10_rand_04.txt |
AC |
10 ms |
3568 KB |
10_rand_05.txt |
AC |
17 ms |
3572 KB |
10_rand_06.txt |
AC |
9 ms |
1784 KB |
10_rand_07.txt |
AC |
17 ms |
2548 KB |
10_rand_08.txt |
AC |
34 ms |
3572 KB |
11_hashi_00.txt |
AC |
19 ms |
2168 KB |
11_hashi_01.txt |
AC |
7 ms |
1404 KB |
11_hashi_02.txt |
AC |
7 ms |
2168 KB |
12_rect_00.txt |
AC |
60 ms |
3572 KB |
12_rect_01.txt |
AC |
9 ms |
1404 KB |
12_rect_02.txt |
AC |
12 ms |
3444 KB |
99_all_one.txt |
AC |
10 ms |
3952 KB |