oj.uz

Submission #355635

# Submission time Handle Problem Language Result Execution time Memory
355635 2021-01-22T23:05:39 Z LucaDantas Skandi (COCI20_skandi) C++17
110 / 110
 148 ms 15868 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 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);
		}
	}

	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:89:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
skandi.cpp:97:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8812 KB Correct.
2 Correct 6 ms 8812 KB Correct.
3 Correct 6 ms 8812 KB Correct.
4 Correct 6 ms 8812 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 6 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 8812 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8812 KB Correct.
2 Correct 6 ms 8812 KB Correct.
3 Correct 6 ms 8940 KB Correct.
4 Correct 7 ms 8812 KB Correct.
5 Correct 6 ms 8940 KB Correct.
6 Correct 7 ms 8832 KB Correct.
7 Correct 7 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 7 ms 8940 KB Correct.
18 Correct 7 ms 8940 KB Correct.
19 Correct 8 ms 8960 KB Correct.
20 Correct 8 ms 8940 KB Correct.
21 Correct 8 ms 8940 KB Correct.
22 Correct 8 ms 8960 KB Correct.
23 Correct 7 ms 8940 KB Correct.
24 Correct 9 ms 8940 KB Correct.
25 Correct 8 ms 8940 KB Correct.
26 Correct 8 ms 8940 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8812 KB Correct.
2 Correct 6 ms 8812 KB Correct.
3 Correct 6 ms 8812 KB Correct.
4 Correct 6 ms 8812 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 6 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 8812 KB Correct.
24 Correct 6 ms 8812 KB Correct.
25 Correct 6 ms 8812 KB Correct.
26 Correct 6 ms 8940 KB Correct.
27 Correct 7 ms 8812 KB Correct.
28 Correct 6 ms 8940 KB Correct.
29 Correct 7 ms 8832 KB Correct.
30 Correct 7 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 7 ms 8940 KB Correct.
41 Correct 7 ms 8940 KB Correct.
42 Correct 8 ms 8960 KB Correct.
43 Correct 8 ms 8940 KB Correct.
44 Correct 8 ms 8940 KB Correct.
45 Correct 8 ms 8960 KB Correct.
46 Correct 7 ms 8940 KB Correct.
47 Correct 9 ms 8940 KB Correct.
48 Correct 8 ms 8940 KB Correct.
49 Correct 8 ms 8940 KB Correct.
50 Correct 63 ms 14628 KB Correct.
51 Correct 148 ms 12396 KB Correct.
52 Correct 86 ms 15132 KB Correct.
53 Correct 65 ms 14700 KB Correct.
54 Correct 78 ms 14316 KB Correct.
55 Correct 84 ms 15492 KB Correct.
56 Correct 71 ms 15252 KB Correct.
57 Correct 79 ms 14932 KB Correct.
58 Correct 147 ms 12140 KB Correct.
59 Correct 64 ms 14260 KB Correct.
60 Correct 78 ms 14992 KB Correct.
61 Correct 83 ms 13788 KB Correct.
62 Correct 75 ms 15120 KB Correct.
63 Correct 71 ms 15212 KB Correct.
64 Correct 46 ms 11116 KB Correct.
65 Correct 68 ms 15144 KB Correct.
66 Correct 86 ms 14396 KB Correct.
67 Correct 88 ms 14656 KB Correct.
68 Correct 84 ms 15496 KB Correct.
69 Correct 72 ms 14744 KB Correct.
70 Correct 74 ms 14868 KB Correct.
71 Correct 93 ms 15512 KB Correct.
72 Correct 73 ms 15468 KB Correct.
73 Correct 100 ms 15856 KB Correct.
74 Correct 105 ms 15408 KB Correct.
75 Correct 98 ms 15868 KB Correct.