oj.uz

Submission #239934

# Submission time Handle Problem Language Result Execution time Memory
239934 2020-06-17T14:16:13 Z Borbi Skandi (COCI20_skandi) C++14
110 / 110
 1464 ms 43512 KB 
#include <bits/stdc++.h>

using namespace std;

/*struct edge
{
	int next, to, flow;
	edge(int _to, int _next, int _flow)
	{
		next = _next; to = _to; flow = _flow;
	}
};*/

const int MAXN = 5e2 + 5;
const int MAXK = 1e6 + 5;

int n, m;
string str[MAXN];
/*edge e[MAXM];
int head[MAXN], br;

void add_edge(int v, int w, int c)
{
	e[br] = edge(w, head[v], c);
	head[v] = br++;
}*/
map <int, pair<int, int> > r_a, c_a;
int cntr, cntc;
int rw[MAXN][MAXN], col[MAXN][MAXN];
vector <int> graph[MAXK];
int vis[MAXK];

void read_input()
{
	cin >> n >> m;

	/*for(int i = 0; i < MAXN; i++)
	{
		head[i] = -1;
	}*/
	for(int i = 0; i < n; i++)
	{
		cin >> str[i];
	}
	for(int i = 1; i < n; i++)
	{
		for(int j = 1; j < m; j++)
		{
			if(str[i][j] == '1') continue;
			if(str[i][j - 1] == '1')
			{
				rw[i][j] = cntr++;
				r_a[cntr - 1] = {i, j};
			}
			else
			{
				rw[i][j] = rw[i][j - 1];
			}
			if(str[i - 1][j] == '1')
			{
				col[i][j] = cntc++;
				c_a[cntc - 1] = {i, j};
			}
			else
			{
				col[i][j] = col[i - 1][j];
			}
		}
	}
	for(int i = 1; i < n; i++)
	{
		for(int j = 1; j < m; j++)
		{
			if(str[i][j] == '0')
			{
				//cout << r_a[rw[i][j]].first << " " << r_a[rw[i][j]].second << " " << c_a[col[i][j]].first << " " << c_a[col[i][j]].second << "\n";
				graph[rw[i][j]].push_back(cntr + col[i][j]);
				graph[cntr + col[i][j]].push_back(rw[i][j]);
			}
		}
	}
	//cout << cntr << " " << cntc << "\n";
}

bool matched[MAXK];
int con[MAXK];
int timer;

bool match(int v)
{
	if(vis[v] == timer) return false;
	vis[v] = timer;
	for(auto x : graph[v])
	{
		if(con[x] == -1 || match(con[x]))
		{
			con[x] = v;
			return matched[v] = true;
		}
	}
	return false;
}

bool added[MAXK];
//vector <int> z;

void dfs(int v, bool t)
{
	if(!added[v])
	{	
		//z.push_back(v);
		added[v] = true;
	}
	else return;
	/*if(t)
	{
		cout << "DAS";
	}*/
	for(auto x : graph[v])
	{
		int tr = 1;
		if(con[x] == -1) tr = 0;
		if(t == 0)
		{
			if(con[x] != v)
				dfs(x, t ^ 1);
			//{
			//}
		}
		else
		{
			int tr = 1;
			if(con[v] == -1) tr = 0;
			if(con[v] == x)
			{
				dfs(x, t ^ 1);
			}
		}
	}
}

void solve()
{
	for(int i = 0; i < MAXK; i++)
	{
		con[i] = -1;
	}
	for(int i = 0; i < cntr; i++)
	{
		timer++;
		match(i);
		//cout << matched[i];
	}
	for(int i = 0; i < cntr; i++)
	{
		if(!matched[i])
		{
			dfs(i, 0);
		}
	}
	vector <int> fst, scnd;
	for(int i = 0; i < cntr; i++)
	{
		if(!added[i])
		{
			fst.push_back(i);
		}
	}
	for(int i = 0; i < cntc; i++)
	{
		if(added[i + cntr])
		{
			scnd.push_back(i);
		}
	}
	cout << fst.size() + scnd.size() << "\n";
	for(auto x : fst)
	{
		cout << r_a[x].first + 1 << " " << r_a[x].second << " DESNO\n"; 
	}
	for(auto x : scnd)
	{
		cout << c_a[x].first << " " << c_a[x].second + 1 << " DOLJE\n"; 
	}
}

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

	read_input();
	solve();

	return 0;
}

Compilation message

skandi.cpp: In function 'void dfs(int, bool)':
skandi.cpp:132:8: warning: variable 'tr' set but not used [-Wunused-but-set-variable]
    int tr = 1;
        ^~
skandi.cpp:121:7: warning: variable 'tr' set but not used [-Wunused-but-set-variable]
   int tr = 1;
       ^~

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28800 KB Correct.
2 Correct 21 ms 28520 KB Correct.
3 Correct 22 ms 29184 KB Correct.
4 Correct 21 ms 28416 KB Correct.
5 Correct 21 ms 28416 KB Correct.
6 Correct 21 ms 28160 KB Correct.
7 Correct 21 ms 28032 KB Correct.
8 Correct 22 ms 28544 KB Correct.
9 Correct 30 ms 29824 KB Correct.
10 Correct 22 ms 29952 KB Correct.
11 Correct 31 ms 29952 KB Correct.
12 Correct 23 ms 29952 KB Correct.
13 Correct 23 ms 29952 KB Correct.
14 Correct 23 ms 29952 KB Correct.
15 Correct 23 ms 30080 KB Correct.
16 Correct 23 ms 29952 KB Correct.
17 Correct 27 ms 29952 KB Correct.
18 Correct 23 ms 29952 KB Correct.
19 Correct 24 ms 30080 KB Correct.
20 Correct 28 ms 29952 KB Correct.
21 Correct 23 ms 29952 KB Correct.
22 Correct 23 ms 29952 KB Correct.
23 Correct 23 ms 29952 KB Correct.
24 Correct 27 ms 29952 KB Correct.
25 Correct 24 ms 29952 KB Correct.
26 Correct 23 ms 30076 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 27776 KB Correct.
2 Correct 24 ms 27776 KB Correct.
3 Correct 22 ms 27776 KB Correct.
4 Correct 20 ms 27776 KB Correct.
5 Correct 21 ms 27776 KB Correct.
6 Correct 20 ms 27776 KB Correct.
7 Correct 21 ms 27776 KB Correct.
8 Correct 20 ms 27776 KB Correct.
9 Correct 21 ms 27776 KB Correct.
10 Correct 21 ms 27776 KB Correct.
11 Correct 20 ms 27776 KB Correct.
12 Correct 21 ms 27776 KB Correct.
13 Correct 21 ms 27776 KB Correct.
14 Correct 21 ms 27776 KB Correct.
15 Correct 25 ms 27776 KB Correct.
16 Correct 24 ms 27776 KB Correct.
17 Correct 25 ms 27776 KB Correct.
18 Correct 21 ms 27776 KB Correct.
19 Correct 21 ms 27776 KB Correct.
20 Correct 25 ms 27776 KB Correct.
21 Correct 21 ms 27776 KB Correct.
22 Correct 21 ms 27776 KB Correct.
23 Correct 24 ms 27776 KB Correct.
24 Correct 21 ms 28800 KB Correct.
25 Correct 21 ms 28520 KB Correct.
26 Correct 22 ms 29184 KB Correct.
27 Correct 21 ms 28416 KB Correct.
28 Correct 21 ms 28416 KB Correct.
29 Correct 21 ms 28160 KB Correct.
30 Correct 21 ms 28032 KB Correct.
31 Correct 22 ms 28544 KB Correct.
32 Correct 30 ms 29824 KB Correct.
33 Correct 22 ms 29952 KB Correct.
34 Correct 31 ms 29952 KB Correct.
35 Correct 23 ms 29952 KB Correct.
36 Correct 23 ms 29952 KB Correct.
37 Correct 23 ms 29952 KB Correct.
38 Correct 23 ms 30080 KB Correct.
39 Correct 23 ms 29952 KB Correct.
40 Correct 27 ms 29952 KB Correct.
41 Correct 23 ms 29952 KB Correct.
42 Correct 24 ms 30080 KB Correct.
43 Correct 28 ms 29952 KB Correct.
44 Correct 23 ms 29952 KB Correct.
45 Correct 23 ms 29952 KB Correct.
46 Correct 23 ms 29952 KB Correct.
47 Correct 27 ms 29952 KB Correct.
48 Correct 24 ms 29952 KB Correct.
49 Correct 23 ms 30076 KB Correct.
50 Correct 76 ms 40820 KB Correct.
51 Correct 736 ms 34856 KB Correct.
52 Correct 90 ms 41716 KB Correct.
53 Correct 82 ms 41204 KB Correct.
54 Correct 91 ms 39800 KB Correct.
55 Correct 90 ms 42872 KB Correct.
56 Correct 87 ms 41972 KB Correct.
57 Correct 83 ms 41592 KB Correct.
58 Correct 1464 ms 34480 KB Correct.
59 Correct 75 ms 40184 KB Correct.
60 Correct 80 ms 41844 KB Correct.
61 Correct 85 ms 38904 KB Correct.
62 Correct 80 ms 41848 KB Correct.
63 Correct 98 ms 42100 KB Correct.
64 Correct 166 ms 32504 KB Correct.
65 Correct 88 ms 41972 KB Correct.
66 Correct 84 ms 39928 KB Correct.
67 Correct 98 ms 40440 KB Correct.
68 Correct 99 ms 42744 KB Correct.
69 Correct 79 ms 41460 KB Correct.
70 Correct 93 ms 41588 KB Correct.
71 Correct 93 ms 42484 KB Correct.
72 Correct 87 ms 42744 KB Correct.
73 Correct 94 ms 43252 KB Correct.
74 Correct 95 ms 42228 KB Correct.
75 Correct 92 ms 43512 KB Correct.