oj.uz

Submission #456279

# Submission time Handle Problem Language Result Execution time Memory
456279 2021-08-06T10:31:49 Z grt Skandi (COCI20_skandi) C++17
9 / 110
 15 ms 14468 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 = 510;
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;
}

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(!vis[i] && match[i] == -1 && aug(i)) any = true;
		}
		if(any) break;
	}
	int ans = 0;
	for(int i = 0; i < n * m; ++i) {
		ans += match[i] != -1;
	}
	cout << ans;
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 12476 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 8 ms 12464 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 8 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 8 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 15 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 7 ms 12532 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 7 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 7 ms 12500 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 7 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 7 ms 12512 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 7 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 7 ms 12536 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 8 ms 12540 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 8 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 8 ms 12564 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 7 ms 12540 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 8 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 10 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 8 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 14468 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 7 ms 13388 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 10 ms 14156 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 8 ms 13316 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 8 ms 13260 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 9 ms 12876 KB First line is correct, but the reconstruction is not properly formatted.
7 Incorrect 8 ms 12876 KB First line is not correct.
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 12476 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 8 ms 12464 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 8 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 8 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 15 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 7 ms 12532 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 7 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 7 ms 12500 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 7 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 7 ms 12512 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 7 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 7 ms 12536 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 8 ms 12540 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 8 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 8 ms 12564 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 7 ms 12540 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 7 ms 12548 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 8 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 10 ms 12492 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 8 ms 12544 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 8 ms 14468 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 7 ms 13388 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 10 ms 14156 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 8 ms 13316 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 8 ms 13260 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 9 ms 12876 KB First line is correct, but the reconstruction is not properly formatted.
30 Incorrect 8 ms 12876 KB First line is not correct.
31 Halted 0 ms 0 KB -