oj.uz

Submission #570657

# Submission time Handle Problem Language Result Execution time Memory
570657 2022-05-30T23:39:14 Z NekoRolly Skandi (COCI20_skandi) C++17
110 / 110
 70 ms 13296 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 dfs1(int u){
	if (!u) return 1;
	for (int v : adj[u]) if (dis[_v[v]] == dis[u]+1 && dfs1(_v[v])){
		_v[v] = u, _u[u] = v;
		return 1;
	}
	dis[u] = inf;
	return 0;
}

void dfs2(int u){ vis[u] = 1;
	for (int v : adj[u]) if (!vis[_v[v]]) dfs2(_v[v]);
}

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] && dfs1(i)) ans++;
	
	cout << ans << "\n";

	for (int u=1; u<=n1; u++) if (!_u[u]) dfs2(u);

	for (int u=1; u<=n1; u++) if (_u[u]){
		if (vis[u])
			cout << posL[_u[u]].first+1 << " " << posL[_u[u]].second << " DESNO\n";
		else
			cout << posU[u].first << " " << posU[u].second+1 << " DOLJE\n"; 
	}

    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Correct.
2 Correct 3 ms 6228 KB Correct.
3 Correct 3 ms 6228 KB Correct.
4 Correct 4 ms 6228 KB Correct.
5 Correct 3 ms 6228 KB Correct.
6 Correct 3 ms 6356 KB Correct.
7 Correct 3 ms 6228 KB Correct.
8 Correct 4 ms 6228 KB Correct.
9 Correct 3 ms 6228 KB Correct.
10 Correct 5 ms 6228 KB Correct.
11 Correct 6 ms 6228 KB Correct.
12 Correct 4 ms 6228 KB Correct.
13 Correct 5 ms 6228 KB Correct.
14 Correct 4 ms 6228 KB Correct.
15 Correct 4 ms 6232 KB Correct.
16 Correct 3 ms 6228 KB Correct.
17 Correct 3 ms 6228 KB Correct.
18 Correct 3 ms 6228 KB Correct.
19 Correct 3 ms 6228 KB Correct.
20 Correct 3 ms 6228 KB Correct.
21 Correct 3 ms 6240 KB Correct.
22 Correct 3 ms 6228 KB Correct.
23 Correct 3 ms 6228 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Correct.
2 Correct 4 ms 7124 KB Correct.
3 Correct 4 ms 7892 KB Correct.
4 Correct 6 ms 7072 KB Correct.
5 Correct 5 ms 6956 KB Correct.
6 Correct 4 ms 6612 KB Correct.
7 Correct 4 ms 6612 KB Correct.
8 Correct 4 ms 7124 KB Correct.
9 Correct 5 ms 8532 KB Correct.
10 Correct 5 ms 8532 KB Correct.
11 Correct 5 ms 8532 KB Correct.
12 Correct 7 ms 8536 KB Correct.
13 Correct 6 ms 8724 KB Correct.
14 Correct 5 ms 8532 KB Correct.
15 Correct 5 ms 8532 KB Correct.
16 Correct 5 ms 8532 KB Correct.
17 Correct 7 ms 8532 KB Correct.
18 Correct 5 ms 8532 KB Correct.
19 Correct 5 ms 8532 KB Correct.
20 Correct 5 ms 8612 KB Correct.
21 Correct 7 ms 8624 KB Correct.
22 Correct 5 ms 8532 KB Correct.
23 Correct 4 ms 8532 KB Correct.
24 Correct 5 ms 8612 KB Correct.
25 Correct 5 ms 8628 KB Correct.
26 Correct 5 ms 8532 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6228 KB Correct.
2 Correct 3 ms 6228 KB Correct.
3 Correct 3 ms 6228 KB Correct.
4 Correct 4 ms 6228 KB Correct.
5 Correct 3 ms 6228 KB Correct.
6 Correct 3 ms 6356 KB Correct.
7 Correct 3 ms 6228 KB Correct.
8 Correct 4 ms 6228 KB Correct.
9 Correct 3 ms 6228 KB Correct.
10 Correct 5 ms 6228 KB Correct.
11 Correct 6 ms 6228 KB Correct.
12 Correct 4 ms 6228 KB Correct.
13 Correct 5 ms 6228 KB Correct.
14 Correct 4 ms 6228 KB Correct.
15 Correct 4 ms 6232 KB Correct.
16 Correct 3 ms 6228 KB Correct.
17 Correct 3 ms 6228 KB Correct.
18 Correct 3 ms 6228 KB Correct.
19 Correct 3 ms 6228 KB Correct.
20 Correct 3 ms 6228 KB Correct.
21 Correct 3 ms 6240 KB Correct.
22 Correct 3 ms 6228 KB Correct.
23 Correct 3 ms 6228 KB Correct.
24 Correct 4 ms 7508 KB Correct.
25 Correct 4 ms 7124 KB Correct.
26 Correct 4 ms 7892 KB Correct.
27 Correct 6 ms 7072 KB Correct.
28 Correct 5 ms 6956 KB Correct.
29 Correct 4 ms 6612 KB Correct.
30 Correct 4 ms 6612 KB Correct.
31 Correct 4 ms 7124 KB Correct.
32 Correct 5 ms 8532 KB Correct.
33 Correct 5 ms 8532 KB Correct.
34 Correct 5 ms 8532 KB Correct.
35 Correct 7 ms 8536 KB Correct.
36 Correct 6 ms 8724 KB Correct.
37 Correct 5 ms 8532 KB Correct.
38 Correct 5 ms 8532 KB Correct.
39 Correct 5 ms 8532 KB Correct.
40 Correct 7 ms 8532 KB Correct.
41 Correct 5 ms 8532 KB Correct.
42 Correct 5 ms 8532 KB Correct.
43 Correct 5 ms 8612 KB Correct.
44 Correct 7 ms 8624 KB Correct.
45 Correct 5 ms 8532 KB Correct.
46 Correct 4 ms 8532 KB Correct.
47 Correct 5 ms 8612 KB Correct.
48 Correct 5 ms 8628 KB Correct.
49 Correct 5 ms 8532 KB Correct.
50 Correct 31 ms 12244 KB Correct.
51 Correct 64 ms 10304 KB Correct.
52 Correct 70 ms 12644 KB Correct.
53 Correct 29 ms 12460 KB Correct.
54 Correct 40 ms 11784 KB Correct.
55 Correct 37 ms 12880 KB Correct.
56 Correct 29 ms 12628 KB Correct.
57 Correct 30 ms 12492 KB Correct.
58 Correct 60 ms 10172 KB Correct.
59 Correct 32 ms 11980 KB Correct.
60 Correct 35 ms 12620 KB Correct.
61 Correct 50 ms 11688 KB Correct.
62 Correct 33 ms 12492 KB Correct.
63 Correct 34 ms 12672 KB Correct.
64 Correct 15 ms 9544 KB Correct.
65 Correct 32 ms 12688 KB Correct.
66 Correct 41 ms 11880 KB Correct.
67 Correct 51 ms 12236 KB Correct.
68 Correct 41 ms 12996 KB Correct.
69 Correct 36 ms 12500 KB Correct.
70 Correct 38 ms 12628 KB Correct.
71 Correct 47 ms 12904 KB Correct.
72 Correct 37 ms 12928 KB Correct.
73 Correct 52 ms 13212 KB Correct.
74 Correct 54 ms 12864 KB Correct.
75 Correct 47 ms 13296 KB Correct.