oj.uz

Submission #667768

# Submission time Handle Problem Language Result Execution time Memory
667768 2022-12-02T02:38:10 Z CSQ31 Skandi (COCI20_skandi) C++17
110 / 110
 1092 ms 107848 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()
{
	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';
	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 13 ms 23764 KB Correct.
3 Correct 14 ms 23764 KB Correct.
4 Correct 14 ms 23736 KB Correct.
5 Correct 13 ms 23764 KB Correct.
6 Correct 13 ms 23764 KB Correct.
7 Correct 13 ms 23764 KB Correct.
8 Correct 14 ms 23764 KB Correct.
9 Correct 13 ms 23764 KB Correct.
10 Correct 15 ms 23816 KB Correct.
11 Correct 13 ms 23768 KB Correct.
12 Correct 14 ms 23764 KB Correct.
13 Correct 14 ms 23776 KB Correct.
14 Correct 14 ms 23768 KB Correct.
15 Correct 17 ms 23764 KB Correct.
16 Correct 13 ms 23764 KB Correct.
17 Correct 16 ms 23928 KB Correct.
18 Correct 16 ms 23764 KB Correct.
19 Correct 14 ms 23764 KB Correct.
20 Correct 14 ms 23768 KB Correct.
21 Correct 13 ms 23824 KB Correct.
22 Correct 13 ms 23832 KB Correct.
23 Correct 13 ms 23764 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24532 KB Correct.
2 Correct 13 ms 24276 KB Correct.
3 Correct 14 ms 24880 KB Correct.
4 Correct 14 ms 24356 KB Correct.
5 Correct 15 ms 24404 KB Correct.
6 Correct 14 ms 24148 KB Correct.
7 Correct 14 ms 24176 KB Correct.
8 Correct 14 ms 24660 KB Correct.
9 Correct 16 ms 26380 KB Correct.
10 Correct 17 ms 26252 KB Correct.
11 Correct 18 ms 26220 KB Correct.
12 Correct 17 ms 26252 KB Correct.
13 Correct 19 ms 26180 KB Correct.
14 Correct 17 ms 26252 KB Correct.
15 Correct 18 ms 26252 KB Correct.
16 Correct 21 ms 26252 KB Correct.
17 Correct 18 ms 26252 KB Correct.
18 Correct 18 ms 26252 KB Correct.
19 Correct 17 ms 26216 KB Correct.
20 Correct 18 ms 26388 KB Correct.
21 Correct 20 ms 26336 KB Correct.
22 Correct 18 ms 26252 KB Correct.
23 Correct 18 ms 26244 KB Correct.
24 Correct 20 ms 26372 KB Correct.
25 Correct 19 ms 26252 KB Correct.
26 Correct 19 ms 26204 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Correct.
2 Correct 13 ms 23764 KB Correct.
3 Correct 14 ms 23764 KB Correct.
4 Correct 14 ms 23736 KB Correct.
5 Correct 13 ms 23764 KB Correct.
6 Correct 13 ms 23764 KB Correct.
7 Correct 13 ms 23764 KB Correct.
8 Correct 14 ms 23764 KB Correct.
9 Correct 13 ms 23764 KB Correct.
10 Correct 15 ms 23816 KB Correct.
11 Correct 13 ms 23768 KB Correct.
12 Correct 14 ms 23764 KB Correct.
13 Correct 14 ms 23776 KB Correct.
14 Correct 14 ms 23768 KB Correct.
15 Correct 17 ms 23764 KB Correct.
16 Correct 13 ms 23764 KB Correct.
17 Correct 16 ms 23928 KB Correct.
18 Correct 16 ms 23764 KB Correct.
19 Correct 14 ms 23764 KB Correct.
20 Correct 14 ms 23768 KB Correct.
21 Correct 13 ms 23824 KB Correct.
22 Correct 13 ms 23832 KB Correct.
23 Correct 13 ms 23764 KB Correct.
24 Correct 13 ms 24532 KB Correct.
25 Correct 13 ms 24276 KB Correct.
26 Correct 14 ms 24880 KB Correct.
27 Correct 14 ms 24356 KB Correct.
28 Correct 15 ms 24404 KB Correct.
29 Correct 14 ms 24148 KB Correct.
30 Correct 14 ms 24176 KB Correct.
31 Correct 14 ms 24660 KB Correct.
32 Correct 16 ms 26380 KB Correct.
33 Correct 17 ms 26252 KB Correct.
34 Correct 18 ms 26220 KB Correct.
35 Correct 17 ms 26252 KB Correct.
36 Correct 19 ms 26180 KB Correct.
37 Correct 17 ms 26252 KB Correct.
38 Correct 18 ms 26252 KB Correct.
39 Correct 21 ms 26252 KB Correct.
40 Correct 18 ms 26252 KB Correct.
41 Correct 18 ms 26252 KB Correct.
42 Correct 17 ms 26216 KB Correct.
43 Correct 18 ms 26388 KB Correct.
44 Correct 20 ms 26336 KB Correct.
45 Correct 18 ms 26252 KB Correct.
46 Correct 18 ms 26244 KB Correct.
47 Correct 20 ms 26372 KB Correct.
48 Correct 19 ms 26252 KB Correct.
49 Correct 19 ms 26204 KB Correct.
50 Correct 289 ms 86864 KB Correct.
51 Correct 1050 ms 102704 KB Correct.
52 Correct 528 ms 106240 KB Correct.
53 Correct 302 ms 88244 KB Correct.
54 Correct 426 ms 102488 KB Correct.
55 Correct 372 ms 105832 KB Correct.
56 Correct 302 ms 106180 KB Correct.
57 Correct 285 ms 105184 KB Correct.
58 Correct 1092 ms 103248 KB Correct.
59 Correct 278 ms 81628 KB Correct.
60 Correct 353 ms 104024 KB Correct.
61 Correct 595 ms 103184 KB Correct.
62 Correct 335 ms 104132 KB Correct.
63 Correct 331 ms 104500 KB Correct.
64 Correct 179 ms 104284 KB Correct.
65 Correct 323 ms 104280 KB Correct.
66 Correct 509 ms 104388 KB Correct.
67 Correct 608 ms 107332 KB Correct.
68 Correct 445 ms 106056 KB Correct.
69 Correct 366 ms 102932 KB Correct.
70 Correct 360 ms 103504 KB Correct.
71 Correct 613 ms 107804 KB Correct.
72 Correct 319 ms 107700 KB Correct.
73 Correct 511 ms 107792 KB Correct.
74 Correct 599 ms 107848 KB Correct.
75 Correct 486 ms 107768 KB Correct.