Submission #1757625
Source Code Expand
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;
typedef vector<int> VI;
typedef vector<char> VB;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define REP(i,n) FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()
const LD eps=1e-5;
//const long long INF=(LL)(1e9)*(LL)(1e9);
const int INF=1e9;
template<class T>
void chmin(T& a, const T& b)
{
if(a>b)
a=b;
}
template<class T>
void chmax(T& a, const T& b)
{
if(a<b)
a=b;
}
const LL pow(const LL p, const LL q)
{
LL t=1;
REP(i,q)
t*=p;
return t;
}
//print for container
/*
template<typename Iterator>
void print(const Iterator& first, const Iterator& last)
{
auto&& back=prev(last);
for(auto e=first; e!=last; e=next(e))
cout<<*e<<" \n"[e==back];
}*/
template<typename Head>
void print(const Head& head)
{
cout<<head<<endl;
}
template<typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail)
{
cout<<head<<" ";
print(tail...);
}
void io_speedup()
{
cin.tie(0);
ios::sync_with_stdio(false);
}
template<typename T>
T read()
{
T t;
cin>>t;
return t;
}
//set INF
using FLOW = long long;
struct Edge
{
int to;
FLOW cap;
int rev;
};
class FlowNetwork
{
public:
FlowNetwork(int n):graph(vector<vector<Edge>>(n)),iter(vector<int>(n)),level(vector<int>(n))
{}
void add_Edge(int from, int to, FLOW cap);
FLOW dinic(int from, int to);
private:
vector<vector<Edge>> graph;
vector<int> iter, level;
FLOW dfs(int from, int to, FLOW cap);
void bfs(int from);
};
void FlowNetwork::add_Edge(int from, int to, FLOW cap)
{
//cout<<from<<":"<<to<<" "<<cap<<endl;
graph[from].push_back((Edge){to,cap,(int)graph[to].size()});
graph[to].push_back((Edge){from,0,(int)graph[from].size()-1});
}
void FlowNetwork::bfs(int from)
{
fill(level.begin(),level.end(),-1);
queue<int> que;
level[from]=0;
que.push(from);
while(!que.empty())
{
int v=que.front();
que.pop();
for(int i=0;i<graph[v].size();i++)
{
Edge &e=graph[v][i];
if(e.cap>0 && level[e.to]<0)
{
level[e.to] = level[v]+1;
que.push(e.to);
}
}
}
}
FLOW FlowNetwork::dfs(int from, int to, FLOW f)
{
if(from == to) return f;
for(int &i=iter[from];i<graph[from].size();i++)
{
Edge &e=graph[from][i];
if(e.cap > 0 && level[from] < level[e.to])
{
FLOW d = dfs(e.to, to, min(e.cap, f));
if(d>0)
{
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
FLOW FlowNetwork::dinic(int from, int to)
{
FLOW flow=0;
while(1)
{
bfs(from);
if(level[to]<0) return flow;
fill(iter.begin(),iter.end(),0);
FLOW f;
while((f=dfs(from,to,INF))>0)
{
flow+=f;
}
}
}
int dx[]={1,0,-1,0}, dy[]={0,1,0,-1};
int main()
{
int h,w;
cin>>h>>w;
auto ptoi=[&](int x,int y)
{
return x*h+y;
};
FlowNetwork flow(w*h*2+2);
REP(j,h)
REP(i,w)
{
REP(k,4)
{
int px=i+dx[k],py=j+dy[k];
if(!(0<=px&&px<w&&0<=py&&py<h)) continue;
flow.add_Edge(ptoi(i,j)+w*h,ptoi(px,py),INF);
}
}
REP(j,h)
{
string s=read<string>();
REP(i,w)
{
if(s[i]=='.')
{
flow.add_Edge(ptoi(i,j),ptoi(i,j)+w*h,1);
}
else
{
flow.add_Edge(ptoi(i,j),ptoi(i,j)+w*h,INF);
flow.add_Edge(ptoi(i,j)+w*h, w*h*2+1, INF);
}
}
}
REP(i,w)
{
flow.add_Edge(w*h*2, ptoi(i,0), INF);
flow.add_Edge(w*h*2, ptoi(i,h-1), INF);
}
REP(j,h)
{
flow.add_Edge(w*h*2, ptoi(0,j), INF);
flow.add_Edge(w*h*2, ptoi(w-1,j), INF);
}
int ans=flow.dinic(w*h*2,w*h*2+1);
if(ans==INF) ans=-1;
cout<<ans<<endl;
}
Submission Info
Submission Time |
|
Task |
E - Fences |
User |
suginamiku |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4185 Byte |
Status |
WA |
Exec Time |
51 ms |
Memory |
5180 KB |
Judge Result
Set Name |
All |
Score / Max Score |
0 / 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 |
256 KB |
10_rand_01.txt |
AC |
2 ms |
512 KB |
10_rand_02.txt |
AC |
11 ms |
1792 KB |
10_rand_03.txt |
AC |
14 ms |
1664 KB |
10_rand_04.txt |
AC |
9 ms |
4608 KB |
10_rand_05.txt |
AC |
13 ms |
4736 KB |
10_rand_06.txt |
AC |
8 ms |
1792 KB |
10_rand_07.txt |
AC |
12 ms |
3072 KB |
10_rand_08.txt |
AC |
22 ms |
4352 KB |
11_hashi_00.txt |
WA |
17 ms |
2432 KB |
11_hashi_01.txt |
WA |
5 ms |
1152 KB |
11_hashi_02.txt |
WA |
7 ms |
2560 KB |
12_rect_00.txt |
AC |
51 ms |
4096 KB |
12_rect_01.txt |
AC |
8 ms |
1280 KB |
12_rect_02.txt |
AC |
10 ms |
3584 KB |
99_all_one.txt |
WA |
10 ms |
5180 KB |