oj.uz

Submission #237786

# Submission time Handle Problem Language Result Execution time Memory
237786 2020-06-08T18:32:44 Z akat Skandi (COCI20_skandi) C++14
110 / 110
 233 ms 13540 KB 
#include<bits/stdc++.h>
using namespace std;
template<class T>
struct MaxFlow 
{
	vector<T>cap;
	vector<int>to,prev,clast,last,level;
	int s,t;
	T INF;
	MaxFlow(int ss,int tt,int n)
	{
		s = ss;
		t = tt;
		INF = 0;
		clast = last = level = vector<int>(n+1,-1);
	}
	void add_edge(int a,int b,T c)
	{
		to.emplace_back(b);
		cap.emplace_back(c);
		prev.emplace_back(last[a]);
		clast[a] = last[a] = to.size() - 1;
		INF = max(INF, c);
	}
	bool bfs()
	{
		static int cnt = 0;
		cnt++;
		int i,x;
		fill(level.begin(), level.end(), 0);
		level[t]=1;
		queue<int>q;
		q.push(t);
		while(q.size())
		{
			x=q.front();
			q.pop();
			for(i=clast[x];i>-1;i=prev[i])
				if(!level[to[i]] && cap[i^1])
				{
					level[to[i]]=level[x]+1;
					q.push(to[i]);
				}
		}
		return level[s]!=0;
	}
	T dfs(int x,T cflow)
	{
		if(x==t)return cflow;
		int i;
		T flow;
		for(i=clast[x];i>-1;i=clast[x]=prev[i])
		{
			if(cap[i] && level[x]==level[to[i]]+1)
			{
				flow=dfs(to[i],min(cflow,cap[i]));
				if(flow)
				{
					cap[i]-=flow;
					cap[i^1]+=flow;
					return flow;
				}
			}
		}
		return 0;
	}
	T maxflow()
	{
		T ans=0,cans;
		while(bfs())
		{
			while((cans=dfs(s,INF)))
				ans+=cans;
			clast = last;
		}
		return ans;
	}
	vector<int> min_vertex_cover()
	{
		vector<int>type(last.size(),2);
		int i, x;
		queue<int>q;
		for(i = last[s]; i > -1; i = prev[i])
		{
			type[to[i]] = 0;
			if(cap[i] == 0) type[to[i]] = 3;
			else q.push(to[i]);
		}
		type[s] = type[t] = 0;
		while(q.size())
		{
			x = q.front();
			q.pop();
			for(i = last[x]; i > -1; i = prev[i])
				if(type[to[i]] > 1)
				{
					if(type[to[i]] == 2)
					{
						type[to[i]] = 1;
						q.push(to[i]);
					}
					else if(cap[i] == 1)
					{
						type[to[i]] = 0;
						q.push(to[i]);
					}
				}
		}
		vector<int>ans;
		for( i = 0; i < (int)last.size(); i++)
			if(type[i] % 2 == 1) ans.emplace_back(i);
		return ans;
	}
};
const int N = 501;
int main()
{
	int n, m, i, j, vert[N][N], horz[N][N], cntv = 0, cnth = 0;
	char c[N][N];
	vector<pair<int,int>> v, h;
	cin>>n>>m;
	for(i = 0 ; i < n; i++)
		for(j = 0; j < m; j++)
		{
			cin>>c[i][j];
			if(c[i][j] == '1')continue;
			if(i != 0)
			{
				if(c[i-1][j] == '1')
				{
					vert[i][j] = cntv++;
					v.push_back({i,j+1});
				}
				else vert[i][j] = vert[i-1][j];
			}
			if(j != 0)
			{
				if(c[i][j-1] == '1')
				{
					horz[i][j] = cnth++;
					h.push_back({i+1,j});
				}
				else horz[i][j] = horz[i][j-1];
			}
		}
	MaxFlow<int>F(0, 1, cntv + cnth + 1);
	for(i = 0 ; i < n; i++)
		for(j = 0; j < m; j++)
			if(c[i][j] == '0') 
			{
				F.add_edge(vert[i][j] + 2, horz[i][j] + cntv + 2, 1);
				F.add_edge(horz[i][j] + cntv + 2, vert[i][j] + 2, 0);
			}
	for(i = 0; i < cntv; i++)
	{
		F.add_edge(0, i + 2, 1);
		F.add_edge(i + 2, 0, 0);
	}
	for(i = 0; i < cnth; i++)
	{
		F.add_edge(i + 2 + cntv, 1, 1);
		F.add_edge(1, i + 2 + cntv, 0);
	}
	cout<<F.maxflow()<<"\n";
	vector<int>cover = F.min_vertex_cover();
	pair<int,int>x;
	for(i = 0; i < (int)cover.size(); i++)
	{
		if(cover[i] >= cntv + 2)
		{
			x = h[cover[i] - 2 - cntv];
			cout<<x.first<<" "<<x.second<<" DESNO\n";
		}
		else
		{
			x = v[cover[i] - 2];
			cout<<x.first<<" "<<x.second<<" DOLJE\n";
		}
	}
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 4 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 4 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 4 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 5 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 5 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 4 ms 384 KB Correct.
14 Correct 4 ms 384 KB Correct.
15 Correct 5 ms 384 KB Correct.
16 Correct 4 ms 384 KB Correct.
17 Correct 4 ms 384 KB Correct.
18 Correct 4 ms 384 KB Correct.
19 Correct 4 ms 384 KB Correct.
20 Correct 4 ms 384 KB Correct.
21 Correct 5 ms 384 KB Correct.
22 Correct 4 ms 384 KB Correct.
23 Correct 5 ms 384 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1664 KB Correct.
2 Correct 5 ms 1152 KB Correct.
3 Correct 6 ms 1920 KB Correct.
4 Correct 5 ms 1152 KB Correct.
5 Correct 5 ms 1024 KB Correct.
6 Correct 5 ms 768 KB Correct.
7 Correct 5 ms 640 KB Correct.
8 Correct 5 ms 1152 KB Correct.
9 Correct 6 ms 2816 KB Correct.
10 Correct 7 ms 2816 KB Correct.
11 Correct 9 ms 2816 KB Correct.
12 Correct 7 ms 2816 KB Correct.
13 Correct 7 ms 2820 KB Correct.
14 Correct 8 ms 2816 KB Correct.
15 Correct 8 ms 2816 KB Correct.
16 Correct 8 ms 2816 KB Correct.
17 Correct 7 ms 2816 KB Correct.
18 Correct 7 ms 2816 KB Correct.
19 Correct 7 ms 2816 KB Correct.
20 Correct 6 ms 2816 KB Correct.
21 Correct 7 ms 2816 KB Correct.
22 Correct 7 ms 2816 KB Correct.
23 Correct 7 ms 2816 KB Correct.
24 Correct 7 ms 2816 KB Correct.
25 Correct 7 ms 2816 KB Correct.
26 Correct 7 ms 2816 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 4 ms 384 KB Correct.
4 Correct 4 ms 384 KB Correct.
5 Correct 4 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 4 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 5 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 5 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 4 ms 384 KB Correct.
14 Correct 4 ms 384 KB Correct.
15 Correct 5 ms 384 KB Correct.
16 Correct 4 ms 384 KB Correct.
17 Correct 4 ms 384 KB Correct.
18 Correct 4 ms 384 KB Correct.
19 Correct 4 ms 384 KB Correct.
20 Correct 4 ms 384 KB Correct.
21 Correct 5 ms 384 KB Correct.
22 Correct 4 ms 384 KB Correct.
23 Correct 5 ms 384 KB Correct.
24 Correct 5 ms 1664 KB Correct.
25 Correct 5 ms 1152 KB Correct.
26 Correct 6 ms 1920 KB Correct.
27 Correct 5 ms 1152 KB Correct.
28 Correct 5 ms 1024 KB Correct.
29 Correct 5 ms 768 KB Correct.
30 Correct 5 ms 640 KB Correct.
31 Correct 5 ms 1152 KB Correct.
32 Correct 6 ms 2816 KB Correct.
33 Correct 7 ms 2816 KB Correct.
34 Correct 9 ms 2816 KB Correct.
35 Correct 7 ms 2816 KB Correct.
36 Correct 7 ms 2820 KB Correct.
37 Correct 8 ms 2816 KB Correct.
38 Correct 8 ms 2816 KB Correct.
39 Correct 8 ms 2816 KB Correct.
40 Correct 7 ms 2816 KB Correct.
41 Correct 7 ms 2816 KB Correct.
42 Correct 7 ms 2816 KB Correct.
43 Correct 6 ms 2816 KB Correct.
44 Correct 7 ms 2816 KB Correct.
45 Correct 7 ms 2816 KB Correct.
46 Correct 7 ms 2816 KB Correct.
47 Correct 7 ms 2816 KB Correct.
48 Correct 7 ms 2816 KB Correct.
49 Correct 7 ms 2816 KB Correct.
50 Correct 77 ms 10620 KB Correct.
51 Correct 233 ms 8728 KB Correct.
52 Correct 126 ms 13136 KB Correct.
53 Correct 70 ms 10708 KB Correct.
54 Correct 103 ms 10832 KB Correct.
55 Correct 101 ms 12160 KB Correct.
56 Correct 77 ms 11092 KB Correct.
57 Correct 71 ms 10956 KB Correct.
58 Correct 228 ms 8600 KB Correct.
59 Correct 80 ms 10532 KB Correct.
60 Correct 77 ms 11408 KB Correct.
61 Correct 140 ms 10836 KB Correct.
62 Correct 80 ms 11348 KB Correct.
63 Correct 81 ms 11600 KB Correct.
64 Correct 46 ms 8260 KB Correct.
65 Correct 78 ms 11472 KB Correct.
66 Correct 124 ms 11340 KB Correct.
67 Correct 164 ms 12884 KB Correct.
68 Correct 100 ms 12372 KB Correct.
69 Correct 86 ms 11216 KB Correct.
70 Correct 81 ms 11348 KB Correct.
71 Correct 163 ms 13268 KB Correct.
72 Correct 74 ms 11728 KB Correct.
73 Correct 130 ms 13540 KB Correct.
74 Correct 157 ms 13272 KB Correct.
75 Correct 112 ms 13140 KB Correct.