oj.uz

Submission #456285

# Submission time Handle Problem Language Result Execution time Memory
456285 2021-08-06T10:51:36 Z grt Skandi (COCI20_skandi) C++17
18 / 110
 33 ms 52044 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 29 ms 48196 KB Correct.
2 Correct 29 ms 48288 KB Correct.
3 Correct 29 ms 48268 KB Correct.
4 Correct 29 ms 48204 KB Correct.
5 Correct 30 ms 48252 KB Correct.
6 Correct 30 ms 48156 KB Correct.
7 Correct 29 ms 48196 KB Correct.
8 Correct 31 ms 48240 KB Correct.
9 Correct 30 ms 48252 KB Correct.
10 Correct 29 ms 48292 KB Correct.
11 Correct 30 ms 48244 KB Correct.
12 Correct 30 ms 48180 KB Correct.
13 Correct 30 ms 48144 KB Correct.
14 Correct 33 ms 48204 KB Correct.
15 Correct 30 ms 48204 KB Correct.
16 Correct 30 ms 48176 KB Correct.
17 Correct 30 ms 48276 KB Correct.
18 Correct 30 ms 48292 KB Correct.
19 Correct 30 ms 48284 KB Correct.
20 Correct 29 ms 48204 KB Correct.
21 Correct 30 ms 48204 KB Correct.
22 Correct 29 ms 48204 KB Correct.
23 Correct 29 ms 48180 KB Correct.

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 52044 KB Correct.
2 Correct 30 ms 49916 KB Correct.
3 Correct 31 ms 51444 KB Correct.
4 Correct 30 ms 49668 KB Correct.
5 Correct 30 ms 49616 KB Correct.
6 Correct 31 ms 49076 KB Correct.
7 Incorrect 30 ms 48864 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 Correct 29 ms 48196 KB Correct.
2 Correct 29 ms 48288 KB Correct.
3 Correct 29 ms 48268 KB Correct.
4 Correct 29 ms 48204 KB Correct.
5 Correct 30 ms 48252 KB Correct.
6 Correct 30 ms 48156 KB Correct.
7 Correct 29 ms 48196 KB Correct.
8 Correct 31 ms 48240 KB Correct.
9 Correct 30 ms 48252 KB Correct.
10 Correct 29 ms 48292 KB Correct.
11 Correct 30 ms 48244 KB Correct.
12 Correct 30 ms 48180 KB Correct.
13 Correct 30 ms 48144 KB Correct.
14 Correct 33 ms 48204 KB Correct.
15 Correct 30 ms 48204 KB Correct.
16 Correct 30 ms 48176 KB Correct.
17 Correct 30 ms 48276 KB Correct.
18 Correct 30 ms 48292 KB Correct.
19 Correct 30 ms 48284 KB Correct.
20 Correct 29 ms 48204 KB Correct.
21 Correct 30 ms 48204 KB Correct.
22 Correct 29 ms 48204 KB Correct.
23 Correct 29 ms 48180 KB Correct.
24 Correct 32 ms 52044 KB Correct.
25 Correct 30 ms 49916 KB Correct.
26 Correct 31 ms 51444 KB Correct.
27 Correct 30 ms 49668 KB Correct.
28 Correct 30 ms 49616 KB Correct.
29 Correct 31 ms 49076 KB Correct.
30 Incorrect 30 ms 48864 KB First line is not correct.
31 Halted 0 ms 0 KB -