oj.uz

Submission #356765

# Submission time Handle Problem Language Result Execution time Memory
356765 2021-01-23T15:43:52 Z LucaDantas Skandi (COCI20_skandi) C++17
50 / 110
 10000 ms 14620 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 dist[match[u]] == dist[u]+1 && dfs(match[u]);
		return 1;
	}
 
	for(int v : g[u]) {
		if(/*mark[v] || */dist[v] != dist[u]+1 || !dfs(v)) continue;
		// printf("%d %d\n", u, v);
		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:99:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
skandi.cpp:107:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |    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 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 7 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 8 ms 8812 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8812 KB Correct.
2 Correct 9 ms 8812 KB Correct.
3 Correct 7 ms 8844 KB Correct.
4 Correct 6 ms 8812 KB Correct.
5 Correct 6 ms 8940 KB Correct.
6 Correct 8 ms 8812 KB Correct.
7 Correct 7 ms 8812 KB Correct.
8 Correct 8 ms 9088 KB Correct.
9 Correct 7 ms 8940 KB Correct.
10 Correct 8 ms 8940 KB Correct.
11 Correct 8 ms 8940 KB Correct.
12 Correct 8 ms 8940 KB Correct.
13 Correct 8 ms 9068 KB Correct.
14 Correct 8 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 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
0.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 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 7 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 8 ms 8812 KB Correct.
24 Correct 8 ms 8812 KB Correct.
25 Correct 9 ms 8812 KB Correct.
26 Correct 7 ms 8844 KB Correct.
27 Correct 6 ms 8812 KB Correct.
28 Correct 6 ms 8940 KB Correct.
29 Correct 8 ms 8812 KB Correct.
30 Correct 7 ms 8812 KB Correct.
31 Correct 8 ms 9088 KB Correct.
32 Correct 7 ms 8940 KB Correct.
33 Correct 8 ms 8940 KB Correct.
34 Correct 8 ms 8940 KB Correct.
35 Correct 8 ms 8940 KB Correct.
36 Correct 8 ms 9068 KB Correct.
37 Correct 8 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 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 94 ms 14620 KB Correct.
51 Execution timed out 10093 ms 11884 KB Time limit exceeded
52 Halted 0 ms 0 KB -