Submission #667766

#	Time	Username	Problem	Language	Result	Execution time	Memory
667766		CSQ31	Skandi (COCI20_skandi)	C++17	110 / 110	1094 ms	108320 KiB

Main

 #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 / 18
• Subtask 2: 32 / 32
• Subtask 3: 60 / 60