oj.uz

Submission #356755

# Submission time Handle Problem Language Result Execution time Memory
356755 2021-01-23T15:28:31 Z LucaDantas Skandi (COCI20_skandi) C++17
110 / 110
 181 ms 15476 KB 
#include<bits/stdc++.h>
using namespace std;
 
using pii = pair<int,int>;
 
#define pb push_back
 
constexpr int maxn = 3e5+10, inf = 0x3f3f3f3f;
 
int color[maxn], match[maxn], dist[maxn];
bool mark[maxn];
 
vector<int> g[maxn];

bool bfs(int n) {
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		if(match[i] == 0) {
			dist[i] = 0;
			q.push(i);
		}
		else dist[i] = inf;
	}
	dist[0] = inf;
	while(!q.empty()) {
		int v = q.front(); q.pop();
		for(int u : g[v]) {
			if(dist[match[u]] == inf) {
				dist[match[u]] = dist[v] + 1;
				q.push(match[u]);
			}
		}
	}
	return (dist[0] != inf);
}

bool dfs(int v){
	if(!v) return 1;
	for(int u : g[v]) {
		if(dist[match[u]] == dist[v] + 1 && dfs(match[u])) {
			match[u] = v;
			match[v] = u;
			return 1;
		}
	}
	dist[v] = inf;
	return 0;
}

int hopcroftKarp(int n) {
	for(int i = 1; i <=n; i++) match[i]=0;
	int matching = 0;
	while(bfs(n)) for(int i = 1; i <=n; i++) if(!match[i] && dfs(i)) matching++;
	return matching;
}

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;
		}
	}
 
	memset(mark, 0, sizeof mark);
	printf("%d\n", hopcroftKarp(ptr-1));
 
	for(int i = 1; i < ptr; i++) {
		if(color[i] || match[i] || mark[i]) continue;
		dfs2(i);
	}
 
	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:76:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |  int n, m; scanf("%d %d", &n, &m);
      |            ~~~~~^~~~~~~~~~~~~~~~~
skandi.cpp:84:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7660 KB Correct.
2 Correct 6 ms 7660 KB Correct.
3 Correct 6 ms 7660 KB Correct.
4 Correct 5 ms 7660 KB Correct.
5 Correct 5 ms 7660 KB Correct.
6 Correct 7 ms 7660 KB Correct.
7 Correct 5 ms 7660 KB Correct.
8 Correct 6 ms 7660 KB Correct.
9 Correct 5 ms 7660 KB Correct.
10 Correct 7 ms 7660 KB Correct.
11 Correct 6 ms 7660 KB Correct.
12 Correct 5 ms 7660 KB Correct.
13 Correct 6 ms 7660 KB Correct.
14 Correct 6 ms 7660 KB Correct.
15 Correct 5 ms 7660 KB Correct.
16 Correct 5 ms 7660 KB Correct.
17 Correct 5 ms 7660 KB Correct.
18 Correct 7 ms 7680 KB Correct.
19 Correct 7 ms 7660 KB Correct.
20 Correct 6 ms 7660 KB Correct.
21 Correct 6 ms 7660 KB Correct.
22 Correct 6 ms 7660 KB Correct.
23 Correct 6 ms 7692 KB Correct.
24 Correct 6 ms 7660 KB Correct.
25 Correct 5 ms 7660 KB Correct.
26 Correct 6 ms 7788 KB Correct.
27 Correct 6 ms 7692 KB Correct.
28 Correct 6 ms 7660 KB Correct.
29 Correct 6 ms 7660 KB Correct.
30 Correct 6 ms 7660 KB Correct.
31 Correct 6 ms 7788 KB Correct.
32 Correct 7 ms 7788 KB Correct.
33 Correct 7 ms 7788 KB Correct.
34 Correct 8 ms 7916 KB Correct.
35 Correct 7 ms 7788 KB Correct.
36 Correct 7 ms 7916 KB Correct.
37 Correct 10 ms 7916 KB Correct.
38 Correct 7 ms 7804 KB Correct.
39 Correct 7 ms 7788 KB Correct.
40 Correct 7 ms 7788 KB Correct.
41 Correct 7 ms 7788 KB Correct.
42 Correct 7 ms 7916 KB Correct.
43 Correct 7 ms 7788 KB Correct.
44 Correct 7 ms 7916 KB Correct.
45 Correct 7 ms 7916 KB Correct.
46 Correct 7 ms 7916 KB Correct.
47 Correct 8 ms 7788 KB Correct.
48 Correct 7 ms 7788 KB Correct.
49 Correct 7 ms 7916 KB Correct.
50 Correct 80 ms 14028 KB Correct.
51 Correct 181 ms 11372 KB Correct.
52 Correct 170 ms 14540 KB Correct.
53 Correct 85 ms 14028 KB Correct.
54 Correct 119 ms 13708 KB Correct.
55 Correct 102 ms 15012 KB Correct.
56 Correct 77 ms 14508 KB Correct.
57 Correct 77 ms 14392 KB Correct.
58 Correct 144 ms 11372 KB Correct.
59 Correct 79 ms 13552 KB Correct.
60 Correct 106 ms 14472 KB Correct.
61 Correct 147 ms 13120 KB Correct.
62 Correct 97 ms 14500 KB Correct.
63 Correct 107 ms 14500 KB Correct.
64 Correct 30 ms 10092 KB Correct.
65 Correct 104 ms 14508 KB Correct.
66 Correct 127 ms 13836 KB Correct.
67 Correct 167 ms 14048 KB Correct.
68 Correct 115 ms 14992 KB Correct.
69 Correct 91 ms 14308 KB Correct.
70 Correct 87 ms 14272 KB Correct.
71 Correct 155 ms 15092 KB Correct.
72 Correct 88 ms 14988 KB Correct.
73 Correct 118 ms 15364 KB Correct.
74 Correct 173 ms 14908 KB Correct.
75 Correct 137 ms 15476 KB Correct.