Submission #668206

#	Time	Username	Problem	Language	Result	Execution time	Memory
668206		CSQ31	Skandi (COCI20_skandi)	C++17	110 / 110	1115 ms	160560 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;
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 / 18
• Subtask 2: 32 / 32
• Subtask 3: 60 / 60