Submission #464097

#	Time	Username	Problem	Language	Result	Execution time	Memory
464097		Jasiekstrz	Skandi (COCI20_skandi)	C++17	110 / 110	152 ms	34164 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=500;
bool t[N+10][N+10];
tuple<int,int,string> prnt[2][N*N+10];
int d[N+10][N+10];
int r[N+10][N+10];
bool vis[2][N*N+10];
int mtch[2][N*N+10];
vector<int> e[N*N+10];
bool dfs(int x)
{
	vis[0][x]=true;
	for(auto v:e[x])
	{
		if(vis[1][v])
			continue;
		vis[1][v]=true;
		if(mtch[1][v]==0 || (!vis[0][mtch[1][v]] && dfs(mtch[1][v])))
		{
			mtch[1][v]=x;
			mtch[0][x]=v;
			return true;
		}
	}
	return false;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;
			cin>>c;
			t[i][j]=(c=='1');
		}
	}
	int nd=0,nr=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			d[i][j]=d[i-1][j];
			r[i][j]=r[i][j-1];
			if(!t[i][j])
			{
				e[d[i][j]].push_back(r[i][j]);
			}
			else
			{
				if(i<n && !t[i+1][j])
				{
					nd++;
					prnt[0][nd]={i,j,"DOLJE"};
					d[i][j]=nd;
				}
				if(j<m && !t[i][j+1])
				{
					nr++;
					prnt[1][nr]={i,j,"DESNO"};
					r[i][j]=nr;
				}
			}
		}
	}
	bool con=true;
	while(con)
	{
		con=false;
		for(int i=1;i<=n*m;i++)
			vis[0][i]=vis[1][i]=false;
		for(int i=1;i<=nd;i++)
		{
			if(mtch[0][i]==0 && !vis[0][i] && dfs(i))
				con=true;
		}
	}
	vector<tuple<int,int,string>> ans;
	for(int i=1;i<=nd;i++)
	{
		if(!vis[0][i] && mtch[0][i]!=0)
			ans.push_back(prnt[0][i]);
	}
	for(int i=1;i<=nr;i++)
	{
		if(vis[1][i] && mtch[1][i]!=0)
			ans.push_back(prnt[1][i]);
	}
	cout<<ans.size()<<"\n";
	for(auto [a,b,c]:ans)
		cout<<a<<" "<<b<<" "<<c<<"\n";
	return 0;
}

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