oj.uz

Submission #456288

# Submission time Handle Problem Language Result Execution time Memory
456288 2021-08-06T10:55:48 Z grt Skandi (COCI20_skandi) C++17
110 / 110
 201 ms 60452 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 1010;
int n, m;
char t[nax][nax];
int lft[nax][nax], up[nax][nax];
vi V[nax * nax * 2];
bool vis[nax * nax * 2];
int match[nax * nax * 2];


bool aug(int x) {
	vis[x] = true;
	for(int nbh : V[x]) if(match[nbh] == -1) {
		match[x] = nbh;
		match[nbh] = x;
		return true;
	}
	for(int nbh : V[x]) if(!vis[match[nbh]]) {
		if(aug(match[nbh])) {
			match[x] = nbh;
			match[nbh] = x;
			return true;
		}
	}
	return false;
}

vi ans;

void dfs(int x) {
	vis[x] = true;
	for(int nbh : V[x]) if(!vis[nbh]) {
		ans.PB(nbh);
		vis[nbh] = true;
		dfs(match[nbh]);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			cin >> t[i][j];
			if(t[i][j] == '1') {
				lft[i][j] = i * m + j;
				up[i][j] = i * m + j;
			} else {
				lft[i][j] = lft[i][j - 1];
				up[i][j] = up[i - 1][j];
				V[up[i][j]].PB(lft[i][j] + n * m);
				V[lft[i][j] + n * m].PB(up[i][j]);
			}
		}
	}
	for(int i = 0; i < n * m * 2; ++i) match[i] = -1;
	while(true) {
		for(int i = 0; i < n * m * 2; ++i) vis[i] = false;
		bool any = false;
		for(int i = 0; i < n * m * 2; ++i) {
			if(match[i] == -1 && aug(i)) any = true;
		}
		if(!any) break;
	}
	for(int i = 0; i < n *m * 2; ++i) vis[i] = false;
	for(int i = 0; i < n * m * 2; ++i) {
		if(!vis[i] && match[i] == -1) {
			dfs(i);
		}
	}
	for(int i = 0; i < n * m * 2; ++i) {
		if(!vis[i]) dfs(i);
	}
	cout << (int)ans.size() << "\n";
	for(int x : ans) {
		bool bit = x < n * m;
		x %= n * m;
		cout << x / m + 1 << " " << x % m + 1<< " " << ((1-bit) ? "DESNO" : "DOLJE") << "\n";
	}
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48332 KB Correct.
2 Correct 30 ms 48168 KB Correct.
3 Correct 26 ms 48248 KB Correct.
4 Correct 27 ms 48288 KB Correct.
5 Correct 27 ms 48280 KB Correct.
6 Correct 26 ms 48280 KB Correct.
7 Correct 27 ms 48288 KB Correct.
8 Correct 26 ms 48276 KB Correct.
9 Correct 26 ms 48160 KB Correct.
10 Correct 27 ms 48228 KB Correct.
11 Correct 26 ms 48296 KB Correct.
12 Correct 26 ms 48248 KB Correct.
13 Correct 26 ms 48204 KB Correct.
14 Correct 29 ms 48192 KB Correct.
15 Correct 26 ms 48188 KB Correct.
16 Correct 28 ms 48180 KB Correct.
17 Correct 28 ms 48264 KB Correct.
18 Correct 26 ms 48280 KB Correct.
19 Correct 26 ms 48228 KB Correct.
20 Correct 28 ms 48204 KB Correct.
21 Correct 26 ms 48240 KB Correct.
22 Correct 27 ms 48208 KB Correct.
23 Correct 28 ms 48176 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 52044 KB Correct.
2 Correct 28 ms 49852 KB Correct.
3 Correct 28 ms 51404 KB Correct.
4 Correct 31 ms 49764 KB Correct.
5 Correct 27 ms 49612 KB Correct.
6 Correct 30 ms 48972 KB Correct.
7 Correct 31 ms 48936 KB Correct.
8 Correct 27 ms 49868 KB Correct.
9 Correct 37 ms 52780 KB Correct.
10 Correct 29 ms 52812 KB Correct.
11 Correct 28 ms 52804 KB Correct.
12 Correct 29 ms 52736 KB Correct.
13 Correct 27 ms 52828 KB Correct.
14 Correct 29 ms 52812 KB Correct.
15 Correct 29 ms 52804 KB Correct.
16 Correct 29 ms 52832 KB Correct.
17 Correct 29 ms 52760 KB Correct.
18 Correct 28 ms 52804 KB Correct.
19 Correct 30 ms 52804 KB Correct.
20 Correct 29 ms 52812 KB Correct.
21 Correct 29 ms 52812 KB Correct.
22 Correct 30 ms 52744 KB Correct.
23 Correct 35 ms 52732 KB Correct.
24 Correct 31 ms 52788 KB Correct.
25 Correct 32 ms 52864 KB Correct.
26 Correct 31 ms 52804 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 48332 KB Correct.
2 Correct 30 ms 48168 KB Correct.
3 Correct 26 ms 48248 KB Correct.
4 Correct 27 ms 48288 KB Correct.
5 Correct 27 ms 48280 KB Correct.
6 Correct 26 ms 48280 KB Correct.
7 Correct 27 ms 48288 KB Correct.
8 Correct 26 ms 48276 KB Correct.
9 Correct 26 ms 48160 KB Correct.
10 Correct 27 ms 48228 KB Correct.
11 Correct 26 ms 48296 KB Correct.
12 Correct 26 ms 48248 KB Correct.
13 Correct 26 ms 48204 KB Correct.
14 Correct 29 ms 48192 KB Correct.
15 Correct 26 ms 48188 KB Correct.
16 Correct 28 ms 48180 KB Correct.
17 Correct 28 ms 48264 KB Correct.
18 Correct 26 ms 48280 KB Correct.
19 Correct 26 ms 48228 KB Correct.
20 Correct 28 ms 48204 KB Correct.
21 Correct 26 ms 48240 KB Correct.
22 Correct 27 ms 48208 KB Correct.
23 Correct 28 ms 48176 KB Correct.
24 Correct 29 ms 52044 KB Correct.
25 Correct 28 ms 49852 KB Correct.
26 Correct 28 ms 51404 KB Correct.
27 Correct 31 ms 49764 KB Correct.
28 Correct 27 ms 49612 KB Correct.
29 Correct 30 ms 48972 KB Correct.
30 Correct 31 ms 48936 KB Correct.
31 Correct 27 ms 49868 KB Correct.
32 Correct 37 ms 52780 KB Correct.
33 Correct 29 ms 52812 KB Correct.
34 Correct 28 ms 52804 KB Correct.
35 Correct 29 ms 52736 KB Correct.
36 Correct 27 ms 52828 KB Correct.
37 Correct 29 ms 52812 KB Correct.
38 Correct 29 ms 52804 KB Correct.
39 Correct 29 ms 52832 KB Correct.
40 Correct 29 ms 52760 KB Correct.
41 Correct 28 ms 52804 KB Correct.
42 Correct 30 ms 52804 KB Correct.
43 Correct 29 ms 52812 KB Correct.
44 Correct 29 ms 52812 KB Correct.
45 Correct 30 ms 52744 KB Correct.
46 Correct 35 ms 52732 KB Correct.
47 Correct 31 ms 52788 KB Correct.
48 Correct 32 ms 52864 KB Correct.
49 Correct 31 ms 52804 KB Correct.
50 Correct 87 ms 58764 KB Correct.
51 Correct 188 ms 57584 KB Correct.
52 Correct 99 ms 59756 KB Correct.
53 Correct 87 ms 59200 KB Correct.
54 Correct 99 ms 58272 KB Correct.
55 Correct 106 ms 59812 KB Correct.
56 Correct 106 ms 59536 KB Correct.
57 Correct 87 ms 59276 KB Correct.
58 Correct 201 ms 57752 KB Correct.
59 Correct 90 ms 58388 KB Correct.
60 Correct 98 ms 59376 KB Correct.
61 Correct 109 ms 58724 KB Correct.
62 Correct 100 ms 59008 KB Correct.
63 Correct 98 ms 59576 KB Correct.
64 Correct 51 ms 57208 KB Correct.
65 Correct 99 ms 59492 KB Correct.
66 Correct 107 ms 58728 KB Correct.
67 Correct 109 ms 59684 KB Correct.
68 Correct 98 ms 60048 KB Correct.
69 Correct 89 ms 59232 KB Correct.
70 Correct 89 ms 59332 KB Correct.
71 Correct 110 ms 60280 KB Correct.
72 Correct 96 ms 60100 KB Correct.
73 Correct 119 ms 60452 KB Correct.
74 Correct 113 ms 60192 KB Correct.
75 Correct 102 ms 60416 KB Correct.