oj.uz

Submission #668206

# Submission time Handle Problem Language Result Execution time Memory
668206 2022-12-03T09:49:26 Z CSQ31 Skandi (COCI20_skandi) C++17
110 / 110
 1115 ms 160560 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;
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);
	}
}
vector<int>min_cover(int n,dinic f){
	for(auto x : f.e){
		if(x.v<n && x.u <2*n){
			if(x.flow == 1){
				adj[x.u].pb(x.v);
				match[x.u] = 1;
				match[x.v] = 1;
			}
			else adj[x.v].pb(x.u);
		}	
	}
	for(int i=0;i<n;i++){
		if(!match[i])dfs(i);
	}
	vector<int>ans;
	for(int i=0;i<n;i++){
		if(match[i] && !vis[i])ans.pb(i);
		if(match[i+n] && vis[i+n])ans.pb(i+n);
	}
	return ans;
}
int main()
{
	owo
	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';
	vector<int>ans = min_cover(n*m,d);
	for(int x:ans){
		if(x<n*m)cout<<(x/m)+1<<" "<<(x%m)+1<<" "<<"DESNO"<<'\n';
		else{
			x-=n*m;
			cout<<(x/m)+1<<" "<<(x%m)+1<<" "<<"DOLJE"<<'\n';
		}
		
	}
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23768 KB Correct.
2 Correct 14 ms 23728 KB Correct.
3 Correct 13 ms 23744 KB Correct.
4 Correct 14 ms 23764 KB Correct.
5 Correct 14 ms 23812 KB Correct.
6 Correct 15 ms 23764 KB Correct.
7 Correct 16 ms 23808 KB Correct.
8 Correct 14 ms 23820 KB Correct.
9 Correct 16 ms 23808 KB Correct.
10 Correct 14 ms 23808 KB Correct.
11 Correct 16 ms 23764 KB Correct.
12 Correct 14 ms 23820 KB Correct.
13 Correct 14 ms 23764 KB Correct.
14 Correct 14 ms 23816 KB Correct.
15 Correct 15 ms 23764 KB Correct.
16 Correct 15 ms 23764 KB Correct.
17 Correct 15 ms 23732 KB Correct.
18 Correct 14 ms 23780 KB Correct.
19 Correct 14 ms 23768 KB Correct.
20 Correct 14 ms 23820 KB Correct.
21 Correct 18 ms 23820 KB Correct.
22 Correct 16 ms 23796 KB Correct.
23 Correct 17 ms 23948 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24772 KB Correct.
2 Correct 15 ms 24456 KB Correct.
3 Correct 16 ms 25320 KB Correct.
4 Correct 16 ms 24532 KB Correct.
5 Correct 16 ms 24588 KB Correct.
6 Correct 16 ms 24276 KB Correct.
7 Correct 15 ms 24276 KB Correct.
8 Correct 16 ms 25016 KB Correct.
9 Correct 19 ms 27660 KB Correct.
10 Correct 19 ms 27328 KB Correct.
11 Correct 19 ms 27336 KB Correct.
12 Correct 21 ms 27464 KB Correct.
13 Correct 18 ms 27276 KB Correct.
14 Correct 22 ms 27404 KB Correct.
15 Correct 25 ms 27468 KB Correct.
16 Correct 21 ms 27480 KB Correct.
17 Correct 20 ms 27464 KB Correct.
18 Correct 20 ms 27524 KB Correct.
19 Correct 19 ms 27376 KB Correct.
20 Correct 20 ms 27452 KB Correct.
21 Correct 19 ms 27404 KB Correct.
22 Correct 19 ms 27348 KB Correct.
23 Correct 22 ms 27332 KB Correct.
24 Correct 23 ms 27572 KB Correct.
25 Correct 21 ms 27464 KB Correct.
26 Correct 19 ms 27288 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23768 KB Correct.
2 Correct 14 ms 23728 KB Correct.
3 Correct 13 ms 23744 KB Correct.
4 Correct 14 ms 23764 KB Correct.
5 Correct 14 ms 23812 KB Correct.
6 Correct 15 ms 23764 KB Correct.
7 Correct 16 ms 23808 KB Correct.
8 Correct 14 ms 23820 KB Correct.
9 Correct 16 ms 23808 KB Correct.
10 Correct 14 ms 23808 KB Correct.
11 Correct 16 ms 23764 KB Correct.
12 Correct 14 ms 23820 KB Correct.
13 Correct 14 ms 23764 KB Correct.
14 Correct 14 ms 23816 KB Correct.
15 Correct 15 ms 23764 KB Correct.
16 Correct 15 ms 23764 KB Correct.
17 Correct 15 ms 23732 KB Correct.
18 Correct 14 ms 23780 KB Correct.
19 Correct 14 ms 23768 KB Correct.
20 Correct 14 ms 23820 KB Correct.
21 Correct 18 ms 23820 KB Correct.
22 Correct 16 ms 23796 KB Correct.
23 Correct 17 ms 23948 KB Correct.
24 Correct 15 ms 24772 KB Correct.
25 Correct 15 ms 24456 KB Correct.
26 Correct 16 ms 25320 KB Correct.
27 Correct 16 ms 24532 KB Correct.
28 Correct 16 ms 24588 KB Correct.
29 Correct 16 ms 24276 KB Correct.
30 Correct 15 ms 24276 KB Correct.
31 Correct 16 ms 25016 KB Correct.
32 Correct 19 ms 27660 KB Correct.
33 Correct 19 ms 27328 KB Correct.
34 Correct 19 ms 27336 KB Correct.
35 Correct 21 ms 27464 KB Correct.
36 Correct 18 ms 27276 KB Correct.
37 Correct 22 ms 27404 KB Correct.
38 Correct 25 ms 27468 KB Correct.
39 Correct 21 ms 27480 KB Correct.
40 Correct 20 ms 27464 KB Correct.
41 Correct 20 ms 27524 KB Correct.
42 Correct 19 ms 27376 KB Correct.
43 Correct 20 ms 27452 KB Correct.
44 Correct 19 ms 27404 KB Correct.
45 Correct 19 ms 27348 KB Correct.
46 Correct 22 ms 27332 KB Correct.
47 Correct 23 ms 27572 KB Correct.
48 Correct 21 ms 27464 KB Correct.
49 Correct 19 ms 27288 KB Correct.
50 Correct 338 ms 133520 KB Correct.
51 Correct 1079 ms 140820 KB Correct.
52 Correct 595 ms 152924 KB Correct.
53 Correct 327 ms 135872 KB Correct.
54 Correct 439 ms 135664 KB Correct.
55 Correct 431 ms 147308 KB Correct.
56 Correct 355 ms 145616 KB Correct.
57 Correct 333 ms 142240 KB Correct.
58 Correct 1115 ms 144068 KB Correct.
59 Correct 317 ms 124720 KB Correct.
60 Correct 413 ms 139124 KB Correct.
61 Correct 631 ms 139932 KB Correct.
62 Correct 366 ms 140216 KB Correct.
63 Correct 376 ms 140904 KB Correct.
64 Correct 217 ms 151120 KB Correct.
65 Correct 353 ms 139660 KB Correct.
66 Correct 528 ms 145332 KB Correct.
67 Correct 638 ms 160500 KB Correct.
68 Correct 421 ms 149100 KB Correct.
69 Correct 380 ms 134828 KB Correct.
70 Correct 387 ms 136648 KB Correct.
71 Correct 656 ms 160080 KB Correct.
72 Correct 366 ms 151928 KB Correct.
73 Correct 528 ms 158024 KB Correct.
74 Correct 670 ms 160560 KB Correct.
75 Correct 512 ms 156812 KB Correct.