oj.uz

Submission #570654

# Submission time Handle Problem Language Result Execution time Memory
570654 2022-05-30T23:27:05 Z NekoRolly Skandi (COCI20_skandi) C++17
55 / 110
 78 ms 13132 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e2+4;
const int inf = 1e9;

int n,m,n1,n2,ans;
vector<int> adj[N*N];
int L[N][N],U[N][N];
int _u[N*N],_v[N*N],dis[N*N];
pair<int,int> posU[N*N],posL[N*N];
char lab[N][N];
queue<int> d;
bool vis[N*N];

bool bfs(){
	for (int i=1; i<=n1; i++){
		if (!_u[i]){ dis[i] = 0; d.push(i);}
		else dis[i] = inf;
	}
	dis[0] = inf;
	for (int u; d.size(); d.pop()){ u = d.front();
		for (int v : adj[u]) if (dis[_v[v]] == inf){
			dis[_v[v]] = dis[u] + 1; d.push(_v[v]);
		}
	}
	return dis[0] != inf;
}

bool dfs(int u){
	if (!u) return 1;
	for (int v : adj[u]) if (dis[_v[v]] == dis[u]+1 && dfs(_v[v])){
		_v[v] = u, _u[u] = v;
		return 1;
	}
	dis[u] = inf;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i=0; i<n; i++) for (int j=0; j<m; j++){ cin >> lab[i][j];
		if (lab[i][j] == '0'){
			if (lab[i-1][j] == '0') U[i][j] = U[i-1][j];
			else U[i][j] = ++n1, posU[n1] = {i, j};
			if (lab[i][j-1] == '0') L[i][j] = L[i][j-1];
			else L[i][j] = ++n2, posL[n2] = {i, j};
			adj[U[i][j]].push_back(L[i][j]);
		}
	}

	while (bfs()) for (int i=1; i<=n1; i++)
		if (!_u[i] && dfs(i)) ans++;
	
	cout << ans << "\n";

	for (int u=1; u<=n1; u++) if (_u[u]){ bool f = 0;
		for (int v : adj[u]) if (!_v[v]) f = 1;
		if (f) cout << posU[u].first << " " << posU[u].second+1 << " DOLJE\n";
		else cout << posL[_u[u]].first+1 << " " << posL[_u[u]].second << " DESNO\n";
	}

    return 0;
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Correct.
2 Correct 4 ms 6228 KB Correct.
3 Correct 4 ms 6304 KB Correct.
4 Correct 3 ms 6228 KB Correct.
5 Correct 3 ms 6228 KB Correct.
6 Correct 4 ms 6228 KB Correct.
7 Partially correct 5 ms 6228 KB First line is correct, but the reconstruction is not.
8 Partially correct 4 ms 6228 KB First line is correct, but the reconstruction is not.
9 Correct 3 ms 6228 KB Correct.
10 Correct 3 ms 6228 KB Correct.
11 Correct 3 ms 6228 KB Correct.
12 Partially correct 4 ms 6228 KB First line is correct, but the reconstruction is not.
13 Correct 3 ms 6228 KB Correct.
14 Correct 4 ms 6228 KB Correct.
15 Correct 3 ms 6228 KB Correct.
16 Correct 4 ms 6228 KB Correct.
17 Correct 3 ms 6228 KB Correct.
18 Correct 4 ms 6256 KB Correct.
19 Correct 3 ms 6228 KB Correct.
20 Correct 4 ms 6228 KB Correct.
21 Correct 4 ms 6228 KB Correct.
22 Correct 4 ms 6228 KB Correct.
23 Correct 3 ms 6228 KB Correct.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Correct.
2 Partially correct 4 ms 7124 KB First line is correct, but the reconstruction is not.
3 Partially correct 4 ms 7892 KB First line is correct, but the reconstruction is not.
4 Partially correct 4 ms 6996 KB First line is correct, but the reconstruction is not.
5 Partially correct 4 ms 6996 KB First line is correct, but the reconstruction is not.
6 Partially correct 4 ms 6740 KB First line is correct, but the reconstruction is not.
7 Partially correct 3 ms 6612 KB First line is correct, but the reconstruction is not.
8 Partially correct 4 ms 7124 KB First line is correct, but the reconstruction is not.
9 Partially correct 4 ms 8532 KB First line is correct, but the reconstruction is not.
10 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
11 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
12 Partially correct 4 ms 8532 KB First line is correct, but the reconstruction is not.
13 Partially correct 7 ms 8532 KB First line is correct, but the reconstruction is not.
14 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
15 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
16 Partially correct 5 ms 8540 KB First line is correct, but the reconstruction is not.
17 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
18 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
19 Partially correct 5 ms 8616 KB First line is correct, but the reconstruction is not.
20 Partially correct 5 ms 8592 KB First line is correct, but the reconstruction is not.
21 Partially correct 5 ms 8624 KB First line is correct, but the reconstruction is not.
22 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
23 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
24 Partially correct 6 ms 8532 KB First line is correct, but the reconstruction is not.
25 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
26 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Correct.
2 Correct 4 ms 6228 KB Correct.
3 Correct 4 ms 6304 KB Correct.
4 Correct 3 ms 6228 KB Correct.
5 Correct 3 ms 6228 KB Correct.
6 Correct 4 ms 6228 KB Correct.
7 Partially correct 5 ms 6228 KB First line is correct, but the reconstruction is not.
8 Partially correct 4 ms 6228 KB First line is correct, but the reconstruction is not.
9 Correct 3 ms 6228 KB Correct.
10 Correct 3 ms 6228 KB Correct.
11 Correct 3 ms 6228 KB Correct.
12 Partially correct 4 ms 6228 KB First line is correct, but the reconstruction is not.
13 Correct 3 ms 6228 KB Correct.
14 Correct 4 ms 6228 KB Correct.
15 Correct 3 ms 6228 KB Correct.
16 Correct 4 ms 6228 KB Correct.
17 Correct 3 ms 6228 KB Correct.
18 Correct 4 ms 6256 KB Correct.
19 Correct 3 ms 6228 KB Correct.
20 Correct 4 ms 6228 KB Correct.
21 Correct 4 ms 6228 KB Correct.
22 Correct 4 ms 6228 KB Correct.
23 Correct 3 ms 6228 KB Correct.
24 Correct 4 ms 7508 KB Correct.
25 Partially correct 4 ms 7124 KB First line is correct, but the reconstruction is not.
26 Partially correct 4 ms 7892 KB First line is correct, but the reconstruction is not.
27 Partially correct 4 ms 6996 KB First line is correct, but the reconstruction is not.
28 Partially correct 4 ms 6996 KB First line is correct, but the reconstruction is not.
29 Partially correct 4 ms 6740 KB First line is correct, but the reconstruction is not.
30 Partially correct 3 ms 6612 KB First line is correct, but the reconstruction is not.
31 Partially correct 4 ms 7124 KB First line is correct, but the reconstruction is not.
32 Partially correct 4 ms 8532 KB First line is correct, but the reconstruction is not.
33 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
34 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
35 Partially correct 4 ms 8532 KB First line is correct, but the reconstruction is not.
36 Partially correct 7 ms 8532 KB First line is correct, but the reconstruction is not.
37 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
38 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
39 Partially correct 5 ms 8540 KB First line is correct, but the reconstruction is not.
40 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
41 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
42 Partially correct 5 ms 8616 KB First line is correct, but the reconstruction is not.
43 Partially correct 5 ms 8592 KB First line is correct, but the reconstruction is not.
44 Partially correct 5 ms 8624 KB First line is correct, but the reconstruction is not.
45 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
46 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
47 Partially correct 6 ms 8532 KB First line is correct, but the reconstruction is not.
48 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
49 Partially correct 5 ms 8532 KB First line is correct, but the reconstruction is not.
50 Partially correct 31 ms 12132 KB First line is correct, but the reconstruction is not.
51 Partially correct 78 ms 10220 KB First line is correct, but the reconstruction is not.
52 Partially correct 43 ms 12536 KB First line is correct, but the reconstruction is not.
53 Partially correct 32 ms 12312 KB First line is correct, but the reconstruction is not.
54 Partially correct 39 ms 11708 KB First line is correct, but the reconstruction is not.
55 Partially correct 37 ms 12872 KB First line is correct, but the reconstruction is not.
56 Partially correct 33 ms 12576 KB First line is correct, but the reconstruction is not.
57 Partially correct 30 ms 12500 KB First line is correct, but the reconstruction is not.
58 Partially correct 54 ms 10180 KB First line is correct, but the reconstruction is not.
59 Partially correct 31 ms 11956 KB First line is correct, but the reconstruction is not.
60 Partially correct 35 ms 12488 KB First line is correct, but the reconstruction is not.
61 Partially correct 47 ms 11704 KB First line is correct, but the reconstruction is not.
62 Partially correct 33 ms 12372 KB First line is correct, but the reconstruction is not.
63 Partially correct 33 ms 12588 KB First line is correct, but the reconstruction is not.
64 Partially correct 11 ms 9608 KB First line is correct, but the reconstruction is not.
65 Partially correct 33 ms 12616 KB First line is correct, but the reconstruction is not.
66 Partially correct 48 ms 11856 KB First line is correct, but the reconstruction is not.
67 Partially correct 58 ms 12224 KB First line is correct, but the reconstruction is not.
68 Partially correct 38 ms 12952 KB First line is correct, but the reconstruction is not.
69 Partially correct 36 ms 12400 KB First line is correct, but the reconstruction is not.
70 Partially correct 31 ms 12548 KB First line is correct, but the reconstruction is not.
71 Partially correct 45 ms 12916 KB First line is correct, but the reconstruction is not.
72 Partially correct 33 ms 12880 KB First line is correct, but the reconstruction is not.
73 Partially correct 44 ms 13080 KB First line is correct, but the reconstruction is not.
74 Partially correct 53 ms 12748 KB First line is correct, but the reconstruction is not.
75 Partially correct 50 ms 13132 KB First line is correct, but the reconstruction is not.