oj.uz

Submission #355636

# Submission time Handle Problem Language Result Execution time Memory
355636 2021-01-22T23:07:24 Z LucaDantas Skandi (COCI20_skandi) C++17
110 / 110
 167 ms 15844 KB 
#include<bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

#define pb push_back

constexpr int maxn = 3e5+10;

int color[maxn], match[maxn], dist[maxn];
bool mark[maxn];

vector<int> g[maxn];

bool dfs(int u) {
	mark[u] = 1;

	if(color[u]) {
		if(match[u])
			return dfs(match[u]);
		return 1;
	}

	for(int v : g[u]) {
		if(mark[v] || !dfs(v)) continue;
		match[u] = v, match[v] = u;
		return 1;
	}

	return 0;
}

int last = 0;

int bfs(int n) {
	memset(mark, 0, sizeof mark);
	memset(dist, 0, sizeof dist);
	queue<int> q;

	for(int i = 1; i < n; i++)
		if(!color[i] && !match[i]) q.push(i), mark[i] = 1;
	
	int lim = maxn;

	while(q.size() && dist[q.front()] <= lim) {
		int u = q.front(); q.pop();

		if(color[u]) {
			if(!match[u]) lim = dist[u];
			else if(!mark[match[u]]) q.push(match[u]);
			continue;
		}

		for(int v : g[u]) {
			if(mark[v]) continue;
			mark[v] = 1;
			dist[v] = dist[u]+1;
			q.push(v);
		}
	}

	assert(lim >= last);

	last = lim;

	memset(mark, 0, sizeof mark);

	int ans = 0;
	for(int i = 1; i < n; i++)
		if(!color[i] && !match[i] && !mark[i])
			ans += dfs(i);

	return ans;
}

bool in[maxn];

vector<int> t;

void dfs2(int u) {
	mark[u] = 1;

	if(color[u]) return (void)(t.pb(u), dfs2(match[u]));

	in[u] = 1;
	for(int v : g[u]) {
		if(mark[v]) continue;
		dfs2(v);
	}
}

pii sv[maxn];

int main() {
	int n, m; scanf("%d %d", &n, &m);
	
	vector<int> last_ptr(m), ultimo_c(m);
	ultimo_c[0] = 1;
	int atras = 0, now = 0, ptr = 1;
	
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < m; i++) {
			char c; scanf(" %c", &c);
			int a = c-'0';
			if(a && !atras) now = ptr++;
			if(a && !ultimo_c[i]) ++color[ptr], last_ptr[i] = ptr++;
			else if(!a) {
				g[now].pb(last_ptr[i]), g[last_ptr[i]].pb(now);
				if(sv[now] == make_pair(0, 0))
					sv[now] = {k, i-1};
				if(sv[last_ptr[i]] == make_pair(0, 0))
					sv[last_ptr[i]] = {k-1, i};
			}
			atras = a;
			ultimo_c[i] = a;
		}
	}

	int ans = 0;
	while(1) {
		int here = bfs(ptr);
		if(!here) break;
		ans += here;
	}

	memset(mark, 0, sizeof mark);

	for(int i = 1; i < ptr; i++) {
		if(color[i] || match[i] || mark[i]) continue;
		dfs2(i);
	}

	printf("%d\n", ans);
	for(int i = 1; i < ptr; i++)
		if(!in[i] && !color[i]) printf("%d %d DESNO\n", sv[i].first+1, sv[i].second+1);
	for(int x : t)
		printf("%d %d DOLJE\n", sv[x].first+1, sv[x].second+1);	
}

Compilation message

skandi.cpp: In function 'int main()':
skandi.cpp:95:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
skandi.cpp:103:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8812 KB Correct.
2 Correct 6 ms 8812 KB Correct.
3 Correct 5 ms 8812 KB Correct.
4 Correct 6 ms 8832 KB Correct.
5 Correct 6 ms 8812 KB Correct.
6 Correct 6 ms 8812 KB Correct.
7 Correct 6 ms 8812 KB Correct.
8 Correct 6 ms 8812 KB Correct.
9 Correct 6 ms 8812 KB Correct.
10 Correct 6 ms 8812 KB Correct.
11 Correct 6 ms 8812 KB Correct.
12 Correct 6 ms 8812 KB Correct.
13 Correct 6 ms 8812 KB Correct.
14 Correct 6 ms 8812 KB Correct.
15 Correct 6 ms 8812 KB Correct.
16 Correct 6 ms 8812 KB Correct.
17 Correct 6 ms 8812 KB Correct.
18 Correct 7 ms 8812 KB Correct.
19 Correct 6 ms 8812 KB Correct.
20 Correct 6 ms 8812 KB Correct.
21 Correct 6 ms 8812 KB Correct.
22 Correct 6 ms 8812 KB Correct.
23 Correct 6 ms 8832 KB Correct.
24 Correct 6 ms 8812 KB Correct.
25 Correct 7 ms 8812 KB Correct.
26 Correct 6 ms 8940 KB Correct.
27 Correct 6 ms 8812 KB Correct.
28 Correct 6 ms 8940 KB Correct.
29 Correct 6 ms 8812 KB Correct.
30 Correct 6 ms 8812 KB Correct.
31 Correct 7 ms 8940 KB Correct.
32 Correct 7 ms 8940 KB Correct.
33 Correct 7 ms 8940 KB Correct.
34 Correct 7 ms 8940 KB Correct.
35 Correct 7 ms 8940 KB Correct.
36 Correct 7 ms 8940 KB Correct.
37 Correct 7 ms 8940 KB Correct.
38 Correct 8 ms 8940 KB Correct.
39 Correct 8 ms 8940 KB Correct.
40 Correct 8 ms 8940 KB Correct.
41 Correct 7 ms 8940 KB Correct.
42 Correct 8 ms 8940 KB Correct.
43 Correct 8 ms 8940 KB Correct.
44 Correct 7 ms 8940 KB Correct.
45 Correct 7 ms 8940 KB Correct.
46 Correct 9 ms 8940 KB Correct.
47 Correct 7 ms 8940 KB Correct.
48 Correct 7 ms 8940 KB Correct.
49 Correct 7 ms 8940 KB Correct.
50 Correct 66 ms 14628 KB Correct.
51 Correct 167 ms 12396 KB Correct.
52 Correct 88 ms 15132 KB Correct.
53 Correct 64 ms 14700 KB Correct.
54 Correct 74 ms 14316 KB Correct.
55 Correct 80 ms 15492 KB Correct.
56 Correct 70 ms 14996 KB Correct.
57 Correct 69 ms 14864 KB Correct.
58 Correct 156 ms 12288 KB Correct.
59 Correct 63 ms 14260 KB Correct.
60 Correct 80 ms 15004 KB Correct.
61 Correct 74 ms 13788 KB Correct.
62 Correct 74 ms 15120 KB Correct.
63 Correct 84 ms 15364 KB Correct.
64 Correct 52 ms 11244 KB Correct.
65 Correct 73 ms 14996 KB Correct.
66 Correct 83 ms 14396 KB Correct.
67 Correct 89 ms 14656 KB Correct.
68 Correct 93 ms 15528 KB Correct.
69 Correct 75 ms 14872 KB Correct.
70 Correct 71 ms 14868 KB Correct.
71 Correct 95 ms 15512 KB Correct.
72 Correct 75 ms 15468 KB Correct.
73 Correct 98 ms 15752 KB Correct.
74 Correct 92 ms 15408 KB Correct.
75 Correct 100 ms 15844 KB Correct.