oj.uz

Submission #355634

# Submission time Handle Problem Language Result Execution time Memory
355634 2021-01-22T23:01:11 Z LucaDantas Skandi (COCI20_skandi) C++17
110 / 110
 162 ms 15996 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] || dist[v] != dist[u]+1 || !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 8832 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 8940 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 8832 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 6 ms 8812 KB Correct.
7 Correct 7 ms 8960 KB Correct.
8 Correct 6 ms 8940 KB Correct.
9 Correct 7 ms 8940 KB Correct.
10 Correct 7 ms 8960 KB Correct.
11 Correct 9 ms 8940 KB Correct.
12 Correct 9 ms 9068 KB Correct.
13 Correct 8 ms 8940 KB Correct.
14 Correct 7 ms 8940 KB Correct.
15 Correct 7 ms 8940 KB Correct.
16 Correct 7 ms 8940 KB Correct.
17 Correct 8 ms 8940 KB Correct.
18 Correct 9 ms 8940 KB Correct.
19 Correct 7 ms 8940 KB Correct.
20 Correct 7 ms 8940 KB Correct.
21 Correct 8 ms 8940 KB Correct.
22 Correct 7 ms 8940 KB Correct.
23 Correct 7 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 6 ms 8812 KB Correct.
2 Correct 6 ms 8832 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 8940 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 8832 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 6 ms 8812 KB Correct.
30 Correct 7 ms 8960 KB Correct.
31 Correct 6 ms 8940 KB Correct.
32 Correct 7 ms 8940 KB Correct.
33 Correct 7 ms 8960 KB Correct.
34 Correct 9 ms 8940 KB Correct.
35 Correct 9 ms 9068 KB Correct.
36 Correct 8 ms 8940 KB Correct.
37 Correct 7 ms 8940 KB Correct.
38 Correct 7 ms 8940 KB Correct.
39 Correct 7 ms 8940 KB Correct.
40 Correct 8 ms 8940 KB Correct.
41 Correct 9 ms 8940 KB Correct.
42 Correct 7 ms 8940 KB Correct.
43 Correct 7 ms 8940 KB Correct.
44 Correct 8 ms 8940 KB Correct.
45 Correct 7 ms 8940 KB Correct.
46 Correct 7 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 69 ms 14732 KB Correct.
51 Correct 155 ms 12396 KB Correct.
52 Correct 93 ms 15260 KB Correct.
53 Correct 66 ms 14956 KB Correct.
54 Correct 74 ms 14444 KB Correct.
55 Correct 82 ms 15620 KB Correct.
56 Correct 68 ms 15124 KB Correct.
57 Correct 71 ms 14992 KB Correct.
58 Correct 162 ms 12396 KB Correct.
59 Correct 65 ms 14388 KB Correct.
60 Correct 76 ms 15120 KB Correct.
61 Correct 84 ms 13916 KB Correct.
62 Correct 79 ms 15248 KB Correct.
63 Correct 77 ms 15340 KB Correct.
64 Correct 50 ms 11264 KB Correct.
65 Correct 76 ms 15116 KB Correct.
66 Correct 98 ms 14544 KB Correct.
67 Correct 102 ms 14912 KB Correct.
68 Correct 86 ms 15664 KB Correct.
69 Correct 77 ms 14872 KB Correct.
70 Correct 74 ms 14996 KB Correct.
71 Correct 94 ms 15640 KB Correct.
72 Correct 74 ms 15596 KB Correct.
73 Correct 94 ms 15880 KB Correct.
74 Correct 92 ms 15536 KB Correct.
75 Correct 93 ms 15996 KB Correct.