oj.uz

Submission #356761

# Submission time Handle Problem Language Result Execution time Memory
356761 2021-01-23T15:39:36 Z LucaDantas Skandi (COCI20_skandi) C++17
110 / 110
 155 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] || dist[v] != dist[u]+1 || !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/*, printf("inicio %d\n", i)*/;
	
	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]/*, printf("livre %d %d\n", u, dist[u])*/;
			else if(!mark[match[u]]) dist[match[u]] = dist[u]+1, q.push(match[u]);
			continue;
		}
 
		for(int v : g[u]) {
			if(mark[v]) continue;
			mark[v] = 1;
			dist[v] = dist[u]+1;
			// printf("foi uv %d %d\n", u, v);
			q.push(v);
		}
	}

	// while(q.size()) q.pop();

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8812 KB Correct.
2 Correct 7 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 8 ms 8812 KB Correct.
7 Correct 7 ms 8812 KB Correct.
8 Correct 6 ms 8812 KB Correct.
9 Correct 6 ms 8812 KB Correct.
10 Correct 7 ms 8812 KB Correct.
11 Correct 7 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 7 ms 8812 KB Correct.
16 Correct 6 ms 8812 KB Correct.
17 Correct 7 ms 8812 KB Correct.
18 Correct 6 ms 8812 KB Correct.
19 Correct 8 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 7 ms 8940 KB Correct.
4 Correct 8 ms 8812 KB Correct.
5 Correct 8 ms 8940 KB Correct.
6 Correct 7 ms 8812 KB Correct.
7 Correct 8 ms 8812 KB Correct.
8 Correct 7 ms 8940 KB Correct.
9 Correct 7 ms 8940 KB Correct.
10 Correct 9 ms 8940 KB Correct.
11 Correct 10 ms 8940 KB Correct.
12 Correct 8 ms 8940 KB Correct.
13 Correct 8 ms 8940 KB Correct.
14 Correct 9 ms 8940 KB Correct.
15 Correct 8 ms 8940 KB Correct.
16 Correct 9 ms 8940 KB Correct.
17 Correct 8 ms 8940 KB Correct.
18 Correct 8 ms 8940 KB Correct.
19 Correct 8 ms 8940 KB Correct.
20 Correct 8 ms 8940 KB Correct.
21 Correct 8 ms 8940 KB Correct.
22 Correct 8 ms 8940 KB Correct.
23 Correct 8 ms 8940 KB Correct.
24 Correct 8 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 7 ms 8812 KB Correct.
2 Correct 7 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 8 ms 8812 KB Correct.
7 Correct 7 ms 8812 KB Correct.
8 Correct 6 ms 8812 KB Correct.
9 Correct 6 ms 8812 KB Correct.
10 Correct 7 ms 8812 KB Correct.
11 Correct 7 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 7 ms 8812 KB Correct.
16 Correct 6 ms 8812 KB Correct.
17 Correct 7 ms 8812 KB Correct.
18 Correct 6 ms 8812 KB Correct.
19 Correct 8 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 7 ms 8940 KB Correct.
27 Correct 8 ms 8812 KB Correct.
28 Correct 8 ms 8940 KB Correct.
29 Correct 7 ms 8812 KB Correct.
30 Correct 8 ms 8812 KB Correct.
31 Correct 7 ms 8940 KB Correct.
32 Correct 7 ms 8940 KB Correct.
33 Correct 9 ms 8940 KB Correct.
34 Correct 10 ms 8940 KB Correct.
35 Correct 8 ms 8940 KB Correct.
36 Correct 8 ms 8940 KB Correct.
37 Correct 9 ms 8940 KB Correct.
38 Correct 8 ms 8940 KB Correct.
39 Correct 9 ms 8940 KB Correct.
40 Correct 8 ms 8940 KB Correct.
41 Correct 8 ms 8940 KB Correct.
42 Correct 8 ms 8940 KB Correct.
43 Correct 8 ms 8940 KB Correct.
44 Correct 8 ms 8940 KB Correct.
45 Correct 8 ms 8940 KB Correct.
46 Correct 8 ms 8940 KB Correct.
47 Correct 8 ms 8940 KB Correct.
48 Correct 8 ms 8940 KB Correct.
49 Correct 8 ms 8940 KB Correct.
50 Correct 78 ms 14620 KB Correct.
51 Correct 126 ms 12160 KB Correct.
52 Correct 125 ms 15132 KB Correct.
53 Correct 88 ms 14624 KB Correct.
54 Correct 93 ms 14396 KB Correct.
55 Correct 93 ms 15492 KB Correct.
56 Correct 75 ms 15128 KB Correct.
57 Correct 71 ms 14864 KB Correct.
58 Correct 130 ms 12140 KB Correct.
59 Correct 83 ms 14392 KB Correct.
60 Correct 86 ms 14996 KB Correct.
61 Correct 113 ms 14044 KB Correct.
62 Correct 88 ms 15132 KB Correct.
63 Correct 126 ms 15212 KB Correct.
64 Correct 33 ms 11116 KB Correct.
65 Correct 97 ms 14992 KB Correct.
66 Correct 140 ms 14396 KB Correct.
67 Correct 110 ms 14648 KB Correct.
68 Correct 99 ms 15496 KB Correct.
69 Correct 89 ms 14748 KB Correct.
70 Correct 102 ms 14868 KB Correct.
71 Correct 133 ms 15512 KB Correct.
72 Correct 77 ms 15364 KB Correct.
73 Correct 155 ms 15752 KB Correct.
74 Correct 146 ms 15416 KB Correct.
75 Correct 122 ms 15868 KB Correct.