oj.uz

Submission #570655

# Submission time Handle Problem Language Result Execution time Memory
570655 2022-05-30T23:28:49 Z NekoRolly Skandi (COCI20_skandi) C++17
55 / 110
 72 ms 13160 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";
		ans--;
	}

	while (ans != 0) ans = ans;

    return 0;
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Correct.
2 Correct 4 ms 6228 KB Correct.
3 Correct 4 ms 6228 KB Correct.
4 Correct 3 ms 6228 KB Correct.
5 Correct 3 ms 6228 KB Correct.
6 Correct 5 ms 6292 KB Correct.
7 Partially correct 4 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 4 ms 6228 KB Correct.
10 Correct 4 ms 6356 KB Correct.
11 Correct 5 ms 6228 KB Correct.
12 Partially correct 4 ms 6228 KB First line is correct, but the reconstruction is not.
13 Correct 4 ms 6228 KB Correct.
14 Correct 4 ms 6228 KB Correct.
15 Correct 5 ms 6256 KB Correct.
16 Correct 3 ms 6228 KB Correct.
17 Correct 4 ms 6228 KB Correct.
18 Correct 3 ms 6228 KB Correct.
19 Correct 5 ms 6336 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 7504 KB Correct.
2 Partially correct 4 ms 7124 KB First line is correct, but the reconstruction is not.
3 Partially correct 6 ms 7892 KB First line is correct, but the reconstruction is not.
4 Partially correct 5 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 4 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 5 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 5 ms 8532 KB First line is correct, but the reconstruction is not.
13 Partially correct 5 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 8532 KB First line is correct, but the reconstruction is not.
17 Partially correct 6 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 8532 KB First line is correct, but the reconstruction is not.
20 Partially correct 7 ms 8532 KB First line is correct, but the reconstruction is not.
21 Partially correct 6 ms 8532 KB First line is correct, but the reconstruction is not.
22 Partially correct 6 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 5 ms 8532 KB First line is correct, but the reconstruction is not.
25 Partially correct 6 ms 8532 KB First line is correct, but the reconstruction is not.
26 Partially correct 7 ms 8608 KB First line is correct, but the reconstruction is not.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Correct.
2 Correct 4 ms 6228 KB Correct.
3 Correct 4 ms 6228 KB Correct.
4 Correct 3 ms 6228 KB Correct.
5 Correct 3 ms 6228 KB Correct.
6 Correct 5 ms 6292 KB Correct.
7 Partially correct 4 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 4 ms 6228 KB Correct.
10 Correct 4 ms 6356 KB Correct.
11 Correct 5 ms 6228 KB Correct.
12 Partially correct 4 ms 6228 KB First line is correct, but the reconstruction is not.
13 Correct 4 ms 6228 KB Correct.
14 Correct 4 ms 6228 KB Correct.
15 Correct 5 ms 6256 KB Correct.
16 Correct 3 ms 6228 KB Correct.
17 Correct 4 ms 6228 KB Correct.
18 Correct 3 ms 6228 KB Correct.
19 Correct 5 ms 6336 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 7504 KB Correct.
25 Partially correct 4 ms 7124 KB First line is correct, but the reconstruction is not.
26 Partially correct 6 ms 7892 KB First line is correct, but the reconstruction is not.
27 Partially correct 5 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 4 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 5 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 5 ms 8532 KB First line is correct, but the reconstruction is not.
36 Partially correct 5 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 8532 KB First line is correct, but the reconstruction is not.
40 Partially correct 6 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 8532 KB First line is correct, but the reconstruction is not.
43 Partially correct 7 ms 8532 KB First line is correct, but the reconstruction is not.
44 Partially correct 6 ms 8532 KB First line is correct, but the reconstruction is not.
45 Partially correct 6 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 5 ms 8532 KB First line is correct, but the reconstruction is not.
48 Partially correct 6 ms 8532 KB First line is correct, but the reconstruction is not.
49 Partially correct 7 ms 8608 KB First line is correct, but the reconstruction is not.
50 Partially correct 30 ms 12236 KB First line is correct, but the reconstruction is not.
51 Partially correct 72 ms 10188 KB First line is correct, but the reconstruction is not.
52 Partially correct 47 ms 12536 KB First line is correct, but the reconstruction is not.
53 Partially correct 28 ms 12332 KB First line is correct, but the reconstruction is not.
54 Partially correct 55 ms 11716 KB First line is correct, but the reconstruction is not.
55 Partially correct 39 ms 12800 KB First line is correct, but the reconstruction is not.
56 Partially correct 30 ms 12588 KB First line is correct, but the reconstruction is not.
57 Partially correct 27 ms 12500 KB First line is correct, but the reconstruction is not.
58 Partially correct 55 ms 10176 KB First line is correct, but the reconstruction is not.
59 Partially correct 31 ms 11980 KB First line is correct, but the reconstruction is not.
60 Partially correct 40 ms 12560 KB First line is correct, but the reconstruction is not.
61 Partially correct 51 ms 11644 KB First line is correct, but the reconstruction is not.
62 Partially correct 35 ms 12452 KB First line is correct, but the reconstruction is not.
63 Partially correct 32 ms 12628 KB First line is correct, but the reconstruction is not.
64 Partially correct 13 ms 9552 KB First line is correct, but the reconstruction is not.
65 Partially correct 38 ms 12684 KB First line is correct, but the reconstruction is not.
66 Partially correct 52 ms 11852 KB First line is correct, but the reconstruction is not.
67 Partially correct 53 ms 12212 KB First line is correct, but the reconstruction is not.
68 Partially correct 44 ms 12900 KB First line is correct, but the reconstruction is not.
69 Partially correct 50 ms 12472 KB First line is correct, but the reconstruction is not.
70 Partially correct 44 ms 12492 KB First line is correct, but the reconstruction is not.
71 Partially correct 49 ms 12860 KB First line is correct, but the reconstruction is not.
72 Partially correct 32 ms 12944 KB First line is correct, but the reconstruction is not.
73 Partially correct 47 ms 13140 KB First line is correct, but the reconstruction is not.
74 Partially correct 48 ms 12832 KB First line is correct, but the reconstruction is not.
75 Partially correct 56 ms 13160 KB First line is correct, but the reconstruction is not.