oj.uz

Submission #667766

# Submission time Handle Problem Language Result Execution time Memory
667766 2022-12-02T02:36:03 Z CSQ31 Skandi (COCI20_skandi) C++17
110 / 110
 1094 ms 108320 KB 
 #pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (int)(a.size())
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll A,ll B) {if(!B)return A;return gcd(B,A%B);}
const ll INF = 1e18;
struct flowedge{
	int v,u;
	ll flow = 0,cap = 0;
	flowedge(int _v,int _u,ll _cap){
		v = _v;
		u = _u;
		cap = _cap;
	}
	
};
struct dinic{
	int n,m = 0,s,t;
	vector<flowedge>e;
	vector<int>ptr,level;
	vii adj;
	void add(int v,int u,ll cap){
		e.pb(flowedge(v,u,cap));
		e.pb(flowedge(u,v,0));
		adj[v].pb(m);
		adj[u].pb(++m);
		m++;
	}
	dinic(int _n,int _s,int _t){
		n = _n;
		adj.resize(n);
		ptr.assign(n,0);
		level.assign(n,-1);
		s = _s;
		t = _t;
	}
	void bfs(){
		queue<int>q;
		q.push(s);
		while(!q.empty()){
			int v = q.front();
			q.pop();
			for(int x:adj[v]){
				if(e[x].cap - e[x].flow && level[e[x].u] == -1){
					level[e[x].u] = level[v]+1;
					q.push(e[x].u);
				}
			}
		}
	}
	ll dfs(int v,ll f){
		if(!f)return 0;
		if(v == t)return f;
		for(;ptr[v]<sz(adj[v]);ptr[v]++){
			int i = adj[v][ptr[v]];
			if(e[i].cap - e[i].flow && level[e[i].u] == level[v] + 1){
				ll mn = dfs(e[i].u,min(f,e[i].cap - e[i].flow));
				//cout<<e[i].cap - e[i].flow<<" "<<mn<<'\n';
				if(!mn)continue;
				e[i].flow+=mn;
				e[i^1].flow-=mn;
				return mn;
			} 
		}
		return 0;
	}
	ll flow(){
		ll f = 0;
		while(true){
			for(int i=0;i<n;i++){
				ptr[i] = 0;
				level[i] = -1;
			}
			level[s] = 0;
			bfs();
			//for(int i=0;i<n;i++)cout<<level[i]<<" ";
			//cout<<'\n';
			if(level[t] == -1)break;
			while(true){
				ll x = dfs(s,INF);
				if(!x)break;
				f+=x;
			}
		}
		return f;
		
	}
};
int gg[501][501];
const int MAXN = 1e6+5;
vector<int>adj[MAXN];
bool match[MAXN],vis[MAXN];
void dfs(int v){
	vis[v] = 1;
	for(int x:adj[v]){
		if(!vis[x])dfs(x);
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	vector<string>a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	int s = 2*n*m;
	int t = s+1;
	dinic d(2*n*m+2,s,t);
	for(int i=0;i<n;i++){
		int k = -1;
		for(int j=0;j<m;j++){
			if(a[i][j] == '1')k = j;
			else gg[i][j] = i*m+k;
			d.add(s,i*m+j,1);
			d.add(i*m+j + n*m,t,1);
		}
	}
	for(int j=0;j<m;j++){
		int k = -1;
		for(int i=0;i<n;i++){
			if(a[i][j] == '1')k = i;
			else {
				d.add(gg[i][j],k*m+j + n*m,1);
			}
		}
	}
	cout<<d.flow()<<'\n';
	for(auto x:d.e){
		int v = x.v;
		int u = x.u;
		if(v<n*m && u>=n*m){
			if(x.flow == 1){
				adj[u].pb(v);
				match[u] = 1;
				match[v] = 1;
			}
			else adj[v].pb(u);
		}
	}
	for(int i=0;i<n*m;i++){
		if(!match[i])dfs(i);
	}
	for(int i=0;i<n*m;i++){
		if(match[i] && !vis[i]){
			int x = i/m+1;
			int y = i%m+1;
			cout<<x<<" "<<y<<" DESNO"<<'\n';
		}
	}
	for(int i=0;i<n*m;i++){
		if(match[i+n*m] && vis[i+n*m]){
			int x = i/m+1;
			int y = i%m+1;
			cout<<x<<" "<<y<<" DOLJE"<<'\n';
		}
	}
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Correct.
2 Correct 14 ms 23764 KB Correct.
3 Correct 13 ms 23796 KB Correct.
4 Correct 13 ms 23796 KB Correct.
5 Correct 14 ms 23764 KB Correct.
6 Correct 14 ms 23804 KB Correct.
7 Correct 13 ms 23764 KB Correct.
8 Correct 14 ms 23792 KB Correct.
9 Correct 14 ms 23764 KB Correct.
10 Correct 14 ms 23816 KB Correct.
11 Correct 14 ms 23912 KB Correct.
12 Correct 13 ms 23764 KB Correct.
13 Correct 14 ms 23752 KB Correct.
14 Correct 14 ms 23764 KB Correct.
15 Correct 13 ms 23796 KB Correct.
16 Correct 14 ms 23780 KB Correct.
17 Correct 14 ms 23816 KB Correct.
18 Correct 15 ms 23696 KB Correct.
19 Correct 14 ms 23804 KB Correct.
20 Correct 14 ms 23780 KB Correct.
21 Correct 13 ms 23776 KB Correct.
22 Correct 15 ms 23776 KB Correct.
23 Correct 14 ms 23764 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24552 KB Correct.
2 Correct 13 ms 24336 KB Correct.
3 Correct 16 ms 24948 KB Correct.
4 Correct 15 ms 24300 KB Correct.
5 Correct 15 ms 24420 KB Correct.
6 Correct 14 ms 24148 KB Correct.
7 Correct 14 ms 24044 KB Correct.
8 Correct 14 ms 24660 KB Correct.
9 Correct 17 ms 26508 KB Correct.
10 Correct 18 ms 26164 KB Correct.
11 Correct 18 ms 26200 KB Correct.
12 Correct 18 ms 26292 KB Correct.
13 Correct 18 ms 26164 KB Correct.
14 Correct 17 ms 26252 KB Correct.
15 Correct 18 ms 26252 KB Correct.
16 Correct 18 ms 26280 KB Correct.
17 Correct 19 ms 26292 KB Correct.
18 Correct 18 ms 26288 KB Correct.
19 Correct 18 ms 26252 KB Correct.
20 Correct 18 ms 26252 KB Correct.
21 Correct 18 ms 26252 KB Correct.
22 Correct 18 ms 26248 KB Correct.
23 Correct 17 ms 26288 KB Correct.
24 Correct 18 ms 26292 KB Correct.
25 Correct 18 ms 26380 KB Correct.
26 Correct 20 ms 26168 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Correct.
2 Correct 14 ms 23764 KB Correct.
3 Correct 13 ms 23796 KB Correct.
4 Correct 13 ms 23796 KB Correct.
5 Correct 14 ms 23764 KB Correct.
6 Correct 14 ms 23804 KB Correct.
7 Correct 13 ms 23764 KB Correct.
8 Correct 14 ms 23792 KB Correct.
9 Correct 14 ms 23764 KB Correct.
10 Correct 14 ms 23816 KB Correct.
11 Correct 14 ms 23912 KB Correct.
12 Correct 13 ms 23764 KB Correct.
13 Correct 14 ms 23752 KB Correct.
14 Correct 14 ms 23764 KB Correct.
15 Correct 13 ms 23796 KB Correct.
16 Correct 14 ms 23780 KB Correct.
17 Correct 14 ms 23816 KB Correct.
18 Correct 15 ms 23696 KB Correct.
19 Correct 14 ms 23804 KB Correct.
20 Correct 14 ms 23780 KB Correct.
21 Correct 13 ms 23776 KB Correct.
22 Correct 15 ms 23776 KB Correct.
23 Correct 14 ms 23764 KB Correct.
24 Correct 13 ms 24552 KB Correct.
25 Correct 13 ms 24336 KB Correct.
26 Correct 16 ms 24948 KB Correct.
27 Correct 15 ms 24300 KB Correct.
28 Correct 15 ms 24420 KB Correct.
29 Correct 14 ms 24148 KB Correct.
30 Correct 14 ms 24044 KB Correct.
31 Correct 14 ms 24660 KB Correct.
32 Correct 17 ms 26508 KB Correct.
33 Correct 18 ms 26164 KB Correct.
34 Correct 18 ms 26200 KB Correct.
35 Correct 18 ms 26292 KB Correct.
36 Correct 18 ms 26164 KB Correct.
37 Correct 17 ms 26252 KB Correct.
38 Correct 18 ms 26252 KB Correct.
39 Correct 18 ms 26280 KB Correct.
40 Correct 19 ms 26292 KB Correct.
41 Correct 18 ms 26288 KB Correct.
42 Correct 18 ms 26252 KB Correct.
43 Correct 18 ms 26252 KB Correct.
44 Correct 18 ms 26252 KB Correct.
45 Correct 18 ms 26248 KB Correct.
46 Correct 17 ms 26288 KB Correct.
47 Correct 18 ms 26292 KB Correct.
48 Correct 18 ms 26380 KB Correct.
49 Correct 20 ms 26168 KB Correct.
50 Correct 321 ms 87084 KB Correct.
51 Correct 1014 ms 102820 KB Correct.
52 Correct 541 ms 106688 KB Correct.
53 Correct 299 ms 88552 KB Correct.
54 Correct 420 ms 102636 KB Correct.
55 Correct 379 ms 106052 KB Correct.
56 Correct 303 ms 106584 KB Correct.
57 Correct 302 ms 105380 KB Correct.
58 Correct 1094 ms 103456 KB Correct.
59 Correct 294 ms 81824 KB Correct.
60 Correct 356 ms 104168 KB Correct.
61 Correct 596 ms 103380 KB Correct.
62 Correct 373 ms 104448 KB Correct.
63 Correct 345 ms 104664 KB Correct.
64 Correct 206 ms 104536 KB Correct.
65 Correct 332 ms 104368 KB Correct.
66 Correct 505 ms 104752 KB Correct.
67 Correct 616 ms 107852 KB Correct.
68 Correct 430 ms 106248 KB Correct.
69 Correct 348 ms 103056 KB Correct.
70 Correct 358 ms 103640 KB Correct.
71 Correct 605 ms 108224 KB Correct.
72 Correct 338 ms 108100 KB Correct.
73 Correct 501 ms 108252 KB Correct.
74 Correct 636 ms 108320 KB Correct.
75 Correct 507 ms 108188 KB Correct.