Submission #853128

#	Time	Username	Problem	Language	Result	Execution time	Memory
853128		vjudge1	Skandi (COCI20_skandi)	C++17	110 / 110	4850 ms	79120 KiB

Main

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 505
using namespace std;
const int MX = N * N;
vector <vector<int> > adj(MX * 4), cover(MX * 4);
vector <int> match(MX * 4), vis;

int get(int x, int y) {
	return x * N + y;
}

pair<int, int> reget(int val) {
	if(val > MX) val -= MX;
	return {val / N, val % N};
}

void printp(pair<int,int> a) {
	cout<<a.first<<" "<<a.second<<"\n";
}

bool aug(int node) {
	if(vis[node]) return 0;
	vis[node] = 1;
	for(auto it:adj[node]) {
		if(!match[it] or aug(match[it])) {
			match[it] = node;
			return 1;
		}
	}
	return 0;
}

void solve(set <int> &left, set <int> &right) {
	int ans = 0;
	// ilk önce random greedy matching yap
	for(auto it:left) {
		vector <int> availableNodes;
		for(auto itt:adj[it])
			if(!match[itt]) {
				availableNodes.push_back(itt);
			}

		if(availableNodes.size() == 0) {
			continue;
		}

		ans++;
		int select = availableNodes[rand() % (int)availableNodes.size()];
		match[select] = it;
		match[it] = it;
	}
	for(auto it:left) {
		if(match[it]) continue;
		vis.assign(MX * 4, 0);
		ans += aug(it);
	}
	cout<<ans<<"\n";
	set <int> bnodes = left;
	// build a better adj table
	for(auto it:right) {
		if(match[it]) {
			bnodes.erase(match[it]);
		}
	}
	queue<int> nodes;
	for(auto it:bnodes) {
		nodes.push(it);
	}

	// for every single non-matched left node start a bfs
	vis.assign(MX * 4, 0);
	while(!nodes.empty()) {
		int node = nodes.front();
		nodes.pop();
		vis[node] = 1;
		for(auto it:adj[node]) {
			if(!vis[it] and match[it] != node) {
				vis[it] = 1;
				vis[match[it]] = 1;
				nodes.push(match[it]);
			}
		}
	}

	// get the juice
	for(auto it:left) {
		if(!vis[it]) {
			cout<<(reget(it).first + 1)<<" "<<(reget(it).second + 1)<<" DESNO\n";
		}
	}
	for(auto it:right) {
		if(vis[it]) {
			cout<<(reget(it).first + 1)<<" "<<(reget(it).second + 1)<<" DOLJE\n";
		}
	}

}

int32_t main(){
	fast
	int n, m;
	cin>>n>>m;
	vector <string> s(n);
	for(int i = 0; i < n; i++) {
		cin>>s[i];
	}
	vector <int> col(m); // last bit in this column
	set <int> lnodes, rnodes;
	for(int i = 1; i < n; i++) {
		int prev = 0;
		for(int j = 1; j < m; j++) {
			if(s[i][j] == '1') { 
				col[j] = i;
				prev = j;
			}
			else {
				adj[get(col[j], j)].push_back(MX + get(i, prev));
				adj[MX + get(i, prev)].push_back(get(col[j], j));
				lnodes.insert(MX + get(i, prev));
				rnodes.insert(get(col[j], j));
			}
		}
	}
	solve(lnodes, rnodes);
}

• Subtask 1: 18 / 18
• Subtask 2: 32 / 32
• Subtask 3: 60 / 60