oj.uz

Submission #456282

# Submission time Handle Problem Language Result Execution time Memory
456282 2021-08-06T10:36:38 Z grt Skandi (COCI20_skandi) C++17
9 / 110
 31 ms 51944 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;
}

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;
	}
	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 26 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 26 ms 48176 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 26 ms 48228 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 26 ms 48220 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 27 ms 48196 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 26 ms 48224 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 26 ms 48220 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 31 ms 48224 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 26 ms 48252 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 27 ms 48208 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 26 ms 48236 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 26 ms 48208 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 26 ms 48168 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 26 ms 48196 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 26 ms 48284 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 27 ms 48248 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 26 ms 48196 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 27 ms 48272 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 27 ms 48272 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 28 ms 51944 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 27 ms 49840 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 28 ms 51400 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 28 ms 49716 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 27 ms 49696 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 28 ms 49016 KB First line is correct, but the reconstruction is not properly formatted.
7 Incorrect 27 ms 48920 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 26 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 26 ms 48176 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 26 ms 48228 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 26 ms 48220 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 27 ms 48196 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 26 ms 48224 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 26 ms 48220 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 31 ms 48224 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 26 ms 48252 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 27 ms 48208 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 26 ms 48236 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 26 ms 48208 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 26 ms 48168 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 26 ms 48196 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 26 ms 48284 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 27 ms 48248 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 26 ms 48196 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 27 ms 48204 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 27 ms 48272 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 27 ms 48272 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 28 ms 51944 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 27 ms 49840 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 28 ms 51400 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 28 ms 49716 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 27 ms 49696 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 28 ms 49016 KB First line is correct, but the reconstruction is not properly formatted.
30 Incorrect 27 ms 48920 KB First line is not correct.
31 Halted 0 ms 0 KB -