Submission #570650

#	Time	Username	Problem	Language	Result	Execution time	Memory
570650		NekoRolly	Skandi (COCI20_skandi)	C++17	55 / 110	76 ms	21212 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e2+4;
const int inf = 1e9;

int n,m,n1,n2,ans;
vector<int> adj[N*N],_adj[N*N];
int L[N][N],U[N][N];
int _u[N*N],_v[N*N],dis[N*N];
pair<int,int> posU[N*N],posL[N*N];
char lab[N][N];
queue<int> d;
bool vis[N*N];

bool bfs(){
	for (int i=1; i<=n1; i++){
		if (!_u[i]){ dis[i] = 0; d.push(i);}
		else dis[i] = inf;
	}
	dis[0] = inf;
	for (int u; d.size(); d.pop()){ u = d.front();
		for (int v : adj[u]) if (dis[_v[v]] == inf){
			dis[_v[v]] = dis[u] + 1; d.push(_v[v]);
		}
	}
	return dis[0] != inf;
}

bool dfs(int u){
	if (!u) return 1;
	for (int v : adj[u]) if (dis[_v[v]] == dis[u]+1 && dfs(_v[v])){
		_v[v] = u, _u[u] = v;
		return 1;
	}
	dis[u] = inf;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i=0; i<n; i++) for (int j=0; j<m; j++){ cin >> lab[i][j];
		if (lab[i][j] == '0'){
			if (lab[i-1][j] == '0') U[i][j] = U[i-1][j];
			else U[i][j] = ++n1, posU[n1] = {i, j};
			if (lab[i][j-1] == '0') L[i][j] = L[i][j-1];
			else L[i][j] = ++n2, posL[n2] = {i, j};
			adj[U[i][j]].push_back(L[i][j]);
			_adj[L[i][j]].push_back(U[i][j]);
		}
	}

	while (bfs()) for (int i=1; i<=n1; i++)
		if (!_u[i] && dfs(i)) ans++;
	
	cout << ans << "\n";

	for (int i=1; i<=n1; i++) if (_u[i] && i == _v[_u[i]]) for (int v : adj[i])
		if (!_v[v]){
			cout << posU[i].first << " " << posU[i].second+1 << " DOLJE\n";
			vis[_u[i]] = 1; break;
		}

	for (int i=1; i<=n2; i++) if (_v[i] && i == _u[_v[i]] && !vis[i])
		cout << posL[i].first+1 << " " << posL[i].second << " DESNO\n";

    return 0;
}

• Subtask 1: 9 / 18
• Subtask 2: 16 / 32
• Subtask 3: 30 / 60