oj.uz

Submission #239926

# Submission time Handle Problem Language Result Execution time Memory
239926 2020-06-17T14:02:29 Z Borbi Skandi (COCI20_skandi) C++14
25 / 110
 76 ms 18936 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 = 1e4 + 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[MAXN];
int vis[MAXN];

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[MAXN];
int con[MAXN];
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[MAXN];
//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])
	{
		if(t == 0)
		{
			if(con[x] == -1)
			{
				dfs(x, t ^ 1);
			}
		}
		else
		{
			if(matched[x])
			{
				dfs(x, t ^ 1);
			}
		}
	}
}

void solve()
{
	for(int i = 0; i < MAXN; 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 + 1 << " DESNO\n"; 
	}
	for(auto x : scnd)
	{
		cout << c_a[x].first + 1 << " " << c_a[x].second + 1 << " DOLJE\n"; 
	}
}

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

	read_input();
	solve();

	return 0;
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 6 ms 2304 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 6 ms 2560 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 6 ms 3456 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 6 ms 2048 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 5 ms 2304 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 5 ms 1664 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 5 ms 1536 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 6 ms 2432 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 9 ms 5120 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 8 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 9 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 9 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 9 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 11 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 8 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 5 ms 1024 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 5 ms 896 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 6 ms 2304 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 6 ms 2560 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 6 ms 3456 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 6 ms 2048 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 5 ms 2304 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 5 ms 1664 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 5 ms 1536 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 6 ms 2432 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 9 ms 5120 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 8 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 9 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 9 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 9 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 9 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 11 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 8 ms 5376 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 8 ms 5248 KB First line is correct, but the reconstruction is not properly formatted.
50 Runtime error 76 ms 18936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
51 Halted 0 ms 0 KB -