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
AC × 15
WA × 4
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