oj.uz

Submission #355604

# Submission time Handle Problem Language Result Execution time Memory
355604 2021-01-22T20:02:25 Z LucaDantas Skandi (COCI20_skandi) C++17
110 / 110
 1246 ms 15084 KB 
#include<bits/stdc++.h>
using namespace std;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }

#ifdef MY_DEBUG_FLAG
void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "(" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
#else
#define db(...)
#endif

using pii = pair<int,int>;

#define pb push_back

constexpr int maxn = 3e5+10;

int color[maxn], match[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;
}

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;
	for(int i = 1; i < ptr; i++) {
		if(color[i] || match[i]) continue;
		memset(mark, 0, sizeof mark);
		ans += dfs(i);
	}

	printf("%d\n", ans);

	memset(mark, 0, sizeof mark);

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7660 KB Correct.
2 Correct 5 ms 7660 KB Correct.
3 Correct 5 ms 7660 KB Correct.
4 Correct 5 ms 7660 KB Correct.
5 Correct 5 ms 7660 KB Correct.
6 Correct 6 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 5 ms 7660 KB Correct.
11 Correct 5 ms 7660 KB Correct.
12 Correct 5 ms 7660 KB Correct.
13 Correct 5 ms 7660 KB Correct.
14 Correct 5 ms 7660 KB Correct.
15 Correct 6 ms 7660 KB Correct.
16 Correct 6 ms 7660 KB Correct.
17 Correct 6 ms 7660 KB Correct.
18 Correct 6 ms 7660 KB Correct.
19 Correct 6 ms 7660 KB Correct.
20 Correct 6 ms 7692 KB Correct.
21 Correct 6 ms 7660 KB Correct.
22 Correct 5 ms 7660 KB Correct.
23 Correct 6 ms 7660 KB Correct.

Subtask #2
32.0 / 32.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7660 KB Correct.
2 Correct 5 ms 7660 KB Correct.
3 Correct 5 ms 7660 KB Correct.
4 Correct 5 ms 7660 KB Correct.
5 Correct 5 ms 7660 KB Correct.
6 Correct 6 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 5 ms 7660 KB Correct.
11 Correct 5 ms 7660 KB Correct.
12 Correct 5 ms 7660 KB Correct.
13 Correct 5 ms 7660 KB Correct.
14 Correct 5 ms 7660 KB Correct.
15 Correct 6 ms 7660 KB Correct.
16 Correct 6 ms 7660 KB Correct.
17 Correct 6 ms 7660 KB Correct.
18 Correct 6 ms 7660 KB Correct.
19 Correct 6 ms 7660 KB Correct.
20 Correct 6 ms 7692 KB Correct.
21 Correct 6 ms 7660 KB Correct.
22 Correct 5 ms 7660 KB Correct.
23 Correct 6 ms 7660 KB Correct.
24 Correct 7 ms 7660 KB Correct.
25 Correct 7 ms 7660 KB Correct.
26 Correct 9 ms 7660 KB Correct.
27 Correct 7 ms 7660 KB Correct.
28 Correct 8 ms 7660 KB Correct.
29 Correct 8 ms 7660 KB Correct.
30 Correct 7 ms 7660 KB Correct.
31 Correct 10 ms 7660 KB Correct.
32 Correct 13 ms 7788 KB Correct.
33 Correct 18 ms 7788 KB Correct.
34 Correct 19 ms 7788 KB Correct.
35 Correct 19 ms 7788 KB Correct.
36 Correct 21 ms 7788 KB Correct.
37 Correct 20 ms 7788 KB Correct.
38 Correct 20 ms 7788 KB Correct.
39 Correct 20 ms 7788 KB Correct.
40 Correct 19 ms 7808 KB Correct.
41 Correct 18 ms 7788 KB Correct.
42 Correct 19 ms 7788 KB Correct.
43 Correct 18 ms 7788 KB Correct.
44 Correct 19 ms 7788 KB Correct.
45 Correct 19 ms 7788 KB Correct.
46 Correct 20 ms 7916 KB Correct.
47 Correct 18 ms 7788 KB Correct.
48 Correct 19 ms 7788 KB Correct.
49 Correct 19 ms 7788 KB Correct.
50 Correct 572 ms 13868 KB Correct.
51 Correct 823 ms 11500 KB Correct.
52 Correct 589 ms 14152 KB Correct.
53 Correct 559 ms 13804 KB Correct.
54 Correct 503 ms 13548 KB Correct.
55 Correct 632 ms 14516 KB Correct.
56 Correct 602 ms 13956 KB Correct.
57 Correct 591 ms 13940 KB Correct.
58 Correct 1246 ms 11372 KB Correct.
59 Correct 524 ms 13236 KB Correct.
60 Correct 597 ms 14060 KB Correct.
61 Correct 440 ms 12816 KB Correct.
62 Correct 620 ms 14188 KB Correct.
63 Correct 604 ms 14060 KB Correct.
64 Correct 82 ms 10092 KB Correct.
65 Correct 598 ms 13984 KB Correct.
66 Correct 505 ms 13420 KB Correct.
67 Correct 509 ms 13676 KB Correct.
68 Correct 636 ms 14592 KB Correct.
69 Correct 584 ms 13832 KB Correct.
70 Correct 584 ms 14008 KB Correct.
71 Correct 620 ms 14700 KB Correct.
72 Correct 658 ms 14416 KB Correct.
73 Correct 677 ms 14828 KB Correct.
74 Correct 602 ms 14576 KB Correct.
75 Correct 694 ms 15084 KB Correct.