Submission #258074

#	Time	Username	Problem	Language	Result	Execution time	Memory
258074		MrRobot_28	Skandi (COCI20_skandi)	C++17	110 / 110	1674 ms	18036 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector <vector <int> > g;
vector <int> mt, used;
vector <vector <int> > g1;
vector <bool> used1;
bool dfs(int v, int cnt)
{
	if(used[v] == cnt)
	{
		return false;
	}
	used[v] = cnt;
	for(int i = 0; i < g[v].size(); i++)
	{
		if(mt[g[v][i]] == -1 || dfs(mt[g[v][i]], cnt))
		{
			mt[g[v][i]] = v;
			return true;
		}
	}
	return false;
}
void dfs1(int v)
{
	used1[v] = 1;
	for(int i = 0; i < g1[v].size(); i++)
	{
		int to = g1[v][i];
		if(!used1[to])
		{
			dfs1(to);
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	vector <vector <char> > A(n, vector <char> (m));
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> A[i][j];
		}
	}
	int cnt = 0;
	int cnt1 = 0;
	vector <vector <int> > num1(n, vector <int> (m)), num2(n, vector <int> (m));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
		{
			if(A[i][j] == '0')
			{
				if(A[i][j - 1] == '1')
				{
					num1[i][j] = cnt;
					cnt1++;
					cnt++;
				}
				else
				{
					num1[i][j] = num1[i][j - 1];
				}
			}
		}
	}
	for(int j = 0; j < m; j++)
	{
		for(int i = 0; i < n; i++)
		{
			if(A[i][j] == '0')
			{
				if(A[i - 1][j] == '1')
				{
					num2[i][j] = cnt;
					cnt++;
				}
				else
				{
					num2[i][j] = num2[i - 1][j];
				}
			}
		}
	}
	g.resize(cnt);
	mt.resize(cnt, -1);
	used.resize(cnt);
	g1.resize(cnt);
	used1.resize(cnt);
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(A[i][j] == '0')
			{
				int a = num1[i][j];
				int b = num2[i][j];
				g[a].push_back(b);
				g[b].push_back(a);
			}
		}
	}
	for(int i = 0; i < cnt1; i++)
	{
		dfs(i, i + 1);
	}
	vector <bool> used2(cnt);
	for(int i = cnt1; i < cnt; i++){
		for(int j = 0; j < g[i].size(); j++)
		{
			if(g[i][j] == mt[i])
			{
				used2[mt[i]] = 1;
				g1[i].push_back(mt[i]);
			}
			else
			{
				g1[g[i][j]].push_back(i);
			}
		}
	}
	for(int i = 0; i < cnt1; i++)
	{
		if(!used2[i])
		{
			dfs1(i);
		}
	}
	vector <pair <int, int> > mass1, mass2;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(A[i][j] == '0' && A[i][j - 1] == '1')
			{
				if(!used1[num1[i][j]])
				{
					mass1.push_back({i + 1, j});
				}
			}
			if(A[i][j] == '0' && A[i - 1][j] == '1')
			{
				if(used1[num2[i][j]])
				{
					mass2.push_back({i, j + 1});
				}
			}
		}
	}
	cout << mass1.size() + mass2.size() << "\n";
	for(int i = 0; i < mass1.size(); i++)
	{
		cout << mass1[i].first << " " << mass1[i].second << " " << "DESNO\n";
	}
	for(int i = 0; i < mass2.size(); i++)
	{
		cout << mass2[i].first << " " << mass2[i].second << " " << "DOLJE\n";
	}
  	return 0;
}

Compilation message (stderr)

skandi.cpp: In function 'bool dfs(int, int)':
skandi.cpp:14:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~
skandi.cpp: In function 'void dfs1(int)':
skandi.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g1[v].size(); i++)
                 ~~^~~~~~~~~~~~~~
skandi.cpp: In function 'int main()':
skandi.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++)
                  ~~^~~~~~~~~~~~~
skandi.cpp:155:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mass1.size(); i++)
                 ~~^~~~~~~~~~~~~~
skandi.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < mass2.size(); i++)
                 ~~^~~~~~~~~~~~~~

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