oj.uz

Submission #258074

# Submission time Handle Problem Language Result Execution time Memory
258074 2020-08-05T10:01:56 Z MrRobot_28 Skandi (COCI20_skandi) C++17
110 / 110
 1674 ms 18036 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Correct.
2 Correct 0 ms 384 KB Correct.
3 Correct 1 ms 384 KB Correct.
4 Correct 1 ms 384 KB Correct.
5 Correct 1 ms 384 KB Correct.
6 Correct 0 ms 384 KB Correct.
7 Correct 0 ms 384 KB Correct.
8 Correct 1 ms 384 KB Correct.
9 Correct 0 ms 384 KB Correct.
10 Correct 0 ms 384 KB Correct.
11 Correct 0 ms 384 KB Correct.
12 Correct 1 ms 384 KB Correct.
13 Correct 0 ms 384 KB Correct.
14 Correct 1 ms 384 KB Correct.
15 Correct 0 ms 384 KB Correct.
16 Correct 1 ms 384 KB Correct.
17 Correct 0 ms 384 KB Correct.
18 Correct 0 ms 384 KB Correct.
19 Correct 0 ms 384 KB Correct.
20 Correct 0 ms 384 KB Correct.
21 Correct 0 ms 384 KB Correct.
22 Correct 0 ms 384 KB Correct.
23 Correct 0 ms 384 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct.
2 Correct 1 ms 384 KB Correct.
3 Correct 1 ms 512 KB Correct.
4 Correct 1 ms 384 KB Correct.
5 Correct 1 ms 384 KB Correct.
6 Correct 1 ms 384 KB Correct.
7 Correct 1 ms 384 KB Correct.
8 Correct 1 ms 512 KB Correct.
9 Correct 2 ms 640 KB Correct.
10 Correct 2 ms 768 KB Correct.
11 Correct 2 ms 768 KB Correct.
12 Correct 2 ms 768 KB Correct.
13 Correct 2 ms 768 KB Correct.
14 Correct 2 ms 768 KB Correct.
15 Correct 2 ms 768 KB Correct.
16 Correct 2 ms 768 KB Correct.
17 Correct 2 ms 768 KB Correct.
18 Correct 2 ms 768 KB Correct.
19 Correct 2 ms 768 KB Correct.
20 Correct 3 ms 640 KB Correct.
21 Correct 2 ms 768 KB Correct.
22 Correct 2 ms 768 KB Correct.
23 Correct 2 ms 768 KB Correct.
24 Correct 5 ms 640 KB Correct.
25 Correct 2 ms 768 KB Correct.
26 Correct 2 ms 896 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Correct.
2 Correct 0 ms 384 KB Correct.
3 Correct 1 ms 384 KB Correct.
4 Correct 1 ms 384 KB Correct.
5 Correct 1 ms 384 KB Correct.
6 Correct 0 ms 384 KB Correct.
7 Correct 0 ms 384 KB Correct.
8 Correct 1 ms 384 KB Correct.
9 Correct 0 ms 384 KB Correct.
10 Correct 0 ms 384 KB Correct.
11 Correct 0 ms 384 KB Correct.
12 Correct 1 ms 384 KB Correct.
13 Correct 0 ms 384 KB Correct.
14 Correct 1 ms 384 KB Correct.
15 Correct 0 ms 384 KB Correct.
16 Correct 1 ms 384 KB Correct.
17 Correct 0 ms 384 KB Correct.
18 Correct 0 ms 384 KB Correct.
19 Correct 0 ms 384 KB Correct.
20 Correct 0 ms 384 KB Correct.
21 Correct 0 ms 384 KB Correct.
22 Correct 0 ms 384 KB Correct.
23 Correct 0 ms 384 KB Correct.
24 Correct 1 ms 384 KB Correct.
25 Correct 1 ms 384 KB Correct.
26 Correct 1 ms 512 KB Correct.
27 Correct 1 ms 384 KB Correct.
28 Correct 1 ms 384 KB Correct.
29 Correct 1 ms 384 KB Correct.
30 Correct 1 ms 384 KB Correct.
31 Correct 1 ms 512 KB Correct.
32 Correct 2 ms 640 KB Correct.
33 Correct 2 ms 768 KB Correct.
34 Correct 2 ms 768 KB Correct.
35 Correct 2 ms 768 KB Correct.
36 Correct 2 ms 768 KB Correct.
37 Correct 2 ms 768 KB Correct.
38 Correct 2 ms 768 KB Correct.
39 Correct 2 ms 768 KB Correct.
40 Correct 2 ms 768 KB Correct.
41 Correct 2 ms 768 KB Correct.
42 Correct 2 ms 768 KB Correct.
43 Correct 3 ms 640 KB Correct.
44 Correct 2 ms 768 KB Correct.
45 Correct 2 ms 768 KB Correct.
46 Correct 2 ms 768 KB Correct.
47 Correct 5 ms 640 KB Correct.
48 Correct 2 ms 768 KB Correct.
49 Correct 2 ms 896 KB Correct.
50 Correct 45 ms 14836 KB Correct.
51 Correct 749 ms 8952 KB Correct.
52 Correct 67 ms 16116 KB Correct.
53 Correct 44 ms 14808 KB Correct.
54 Correct 53 ms 14068 KB Correct.
55 Correct 58 ms 17012 KB Correct.
56 Correct 46 ms 15856 KB Correct.
57 Correct 45 ms 15472 KB Correct.
58 Correct 1674 ms 8056 KB Correct.
59 Correct 46 ms 13944 KB Correct.
60 Correct 54 ms 15860 KB Correct.
61 Correct 64 ms 12920 KB Correct.
62 Correct 58 ms 15988 KB Correct.
63 Correct 57 ms 15988 KB Correct.
64 Correct 133 ms 6008 KB Correct.
65 Correct 55 ms 15860 KB Correct.
66 Correct 59 ms 14332 KB Correct.
67 Correct 79 ms 15096 KB Correct.
68 Correct 62 ms 17012 KB Correct.
69 Correct 50 ms 15224 KB Correct.
70 Correct 55 ms 15472 KB Correct.
71 Correct 69 ms 17140 KB Correct.
72 Correct 50 ms 16880 KB Correct.
73 Correct 64 ms 17908 KB Correct.
74 Correct 69 ms 16852 KB Correct.
75 Correct 62 ms 18036 KB Correct.