oj.uz

Submission #710945

# Submission time Handle Problem Language Result Execution time Memory
710945 2023-03-16T06:03:23 Z willychan Skandi (COCI20_skandi) C++14
55 / 110
 373 ms 23964 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

struct DINIC{
	struct edge{
		int to;
		ll cap;
		int rev;
	};
	vector<vector<edge> > side;
	vector<int> level;
	vector<int> next;
	int n;
	void init(int s){
		n = s;
		side.resize(n);
		level.resize(n,0);
		next.resize(n,0);
		for(int i=0;i<n;i++) side[i].clear();
	}
	
	void add_edge(int a,int b,ll c){
		side[a].push_back({b,c,(int)(side[b].size())});
		side[b].push_back({a,0,(int)(side[a].size()-1)});
	}
	
	bool bfs(int s,int t){
		fill(level.begin(),level.end(),-1);
		queue<int> q;
		level[s]=0;
		q.push(s);
		while(q.size()){
			int cur = q.front();
			q.pop();
			for(auto e : side[cur]){
				if(e.cap<=0) continue;
				if(level[e.to]<0){
					level[e.to] = level[cur]+1;
					q.push(e.to);
				}
			}
		}
		return (level[t]!=-1);
	}
	
	ll dfs(int v,int t,ll flow){
		if(v==t) return flow;	
		for(;next[v]<side[v].size();next[v]++){
			auto& e = side[v][next[v]];
			if(e.cap<=0 || level[v]+1!=level[e.to]) continue;	
			ll ans = dfs(e.to,t,min(flow,e.cap));
			if(ans>0){
				e.cap-=ans;
				side[e.to][e.rev].cap+=ans;
				return ans;
			}
		}
		return 0;
	}


	ll flow(int s,int t){
		ll ans= 0;
		while(bfs(s,t)){
			fill(next.begin(),next.end(),0);
			ll f = 0;
			while((f=dfs(s,t,1e18))>0){
				ans+=f;
			}
		}
		return ans;
	}
} G;




pair<int,int> edge[500][500];
int hoz,ver;
bool arr[500][500];
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,m;cin>>n>>m;		
	for(int i=0;i<n;i++){
		string s;cin>>s;
		for(int j=0;j<m;j++) arr[i][j]= (s[j]=='1');
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(arr[i][j]==0) continue;
			int k = i+1;
			while(k<n && arr[k][j]==0){
				if(k==i+1) ++ver;
				edge[k][j].first = ver;
				k++;
			}
			k = j+1;
			while(k<m && arr[i][k]==0){
				if(k==j+1) ++hoz;
				edge[i][k].second = hoz;
				k++;
			}
		}
	}
	G.init(hoz+ver+2);
	for(int i=1;i<=ver;i++){
		G.add_edge(0,i,1);
	}
	for(int i=ver+1;i<=hoz+ver;i++){
		G.add_edge(i,hoz+ver+1,1);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(arr[i][j]) continue;
			G.add_edge(edge[i][j].first,edge[i][j].second+ver,1);
		}
	}
	int ans = G.flow(0,hoz+ver+1);
	cout<<ans<<"\n";
	return 0;
}

Compilation message

skandi.cpp: In member function 'll DINIC::dfs(int, int, ll)':
skandi.cpp:51:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<DINIC::edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(;next[v]<side[v].size();next[v]++){

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 1 ms 332 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 1 ms 332 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 1 ms 332 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 1 ms 212 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 1 ms 328 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 1108 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 1 ms 1108 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 1 ms 1748 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 1 ms 980 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 2 ms 1108 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 1 ms 716 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 1 ms 724 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 1 ms 1236 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 2 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 2 ms 2772 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 2 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 3 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 3 ms 2892 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 2 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 3 ms 2892 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 3 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 2 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 2 ms 2772 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 1 ms 332 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 1 ms 332 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 1 ms 332 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 1 ms 212 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 1 ms 340 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 1 ms 328 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 1 ms 1108 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 1 ms 1108 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 1 ms 1748 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 1 ms 980 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 2 ms 1108 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 1 ms 716 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 1 ms 724 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 1 ms 1236 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 2 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 2 ms 2772 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 2 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 3 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 3 ms 2892 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 2 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 3 ms 2892 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 3 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 2 ms 2896 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 3 ms 2900 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 2 ms 2772 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 81 ms 17708 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 373 ms 17920 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 173 ms 22772 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 76 ms 17644 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 152 ms 19792 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 110 ms 21004 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 76 ms 18404 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 82 ms 18048 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 246 ms 17936 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 99 ms 17792 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 102 ms 19456 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 195 ms 20164 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 102 ms 19732 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 103 ms 19700 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 21 ms 15476 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 91 ms 19392 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 186 ms 21152 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 246 ms 23356 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 131 ms 21760 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 115 ms 19200 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 124 ms 19280 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 190 ms 23964 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 80 ms 19680 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 168 ms 23536 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 207 ms 23956 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 171 ms 22980 KB First line is correct, but the reconstruction is not properly formatted.