oj.uz

Submission #570648

# Submission time Handle Problem Language Result Execution time Memory
570648 2022-05-30T22:38:37 Z NekoRolly Skandi (COCI20_skandi) C++17
55 / 110
 77 ms 21296 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],_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]);
			_adj[L[i][j]].push_back(U[i][j]);
		}
	}

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

	for (int i=1; i<=n1; i++) if (_u[i]) for (int v : adj[i]) if (!_v[v]){
		cout << posU[i].first << " " << posU[i].second+1 << " DOLJE\n";
		vis[_u[i]] = 1; break;
	}

	for (int i=1; i<=n2; i++) if (_v[i] && !vis[i])
		cout << posL[i].first+1 << " " << posL[i].second << " DESNO\n";

    return 0;
}

Subtask #1
9.0 / 18.0

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

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13472 KB Correct.
2 Partially correct 7 ms 13112 KB First line is correct, but the reconstruction is not.
3 Partially correct 8 ms 13780 KB First line is correct, but the reconstruction is not.
4 Partially correct 8 ms 13012 KB First line is correct, but the reconstruction is not.
5 Partially correct 7 ms 13012 KB First line is correct, but the reconstruction is not.
6 Partially correct 7 ms 12628 KB First line is correct, but the reconstruction is not.
7 Partially correct 7 ms 12628 KB First line is correct, but the reconstruction is not.
8 Partially correct 7 ms 13160 KB First line is correct, but the reconstruction is not.
9 Partially correct 9 ms 14588 KB First line is correct, but the reconstruction is not.
10 Partially correct 9 ms 14548 KB First line is correct, but the reconstruction is not.
11 Partially correct 9 ms 14548 KB First line is correct, but the reconstruction is not.
12 Partially correct 10 ms 14548 KB First line is correct, but the reconstruction is not.
13 Partially correct 8 ms 14576 KB First line is correct, but the reconstruction is not.
14 Partially correct 9 ms 14620 KB First line is correct, but the reconstruction is not.
15 Partially correct 8 ms 14620 KB First line is correct, but the reconstruction is not.
16 Partially correct 9 ms 14552 KB First line is correct, but the reconstruction is not.
17 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
18 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
19 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
20 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
21 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
22 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
23 Partially correct 10 ms 14572 KB First line is correct, but the reconstruction is not.
24 Partially correct 8 ms 14588 KB First line is correct, but the reconstruction is not.
25 Partially correct 8 ms 14584 KB First line is correct, but the reconstruction is not.
26 Partially correct 9 ms 14548 KB First line is correct, but the reconstruction is not.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Correct.
2 Correct 7 ms 12232 KB Correct.
3 Correct 8 ms 12244 KB Correct.
4 Correct 7 ms 12244 KB Correct.
5 Correct 7 ms 12244 KB Correct.
6 Correct 7 ms 12244 KB Correct.
7 Partially correct 7 ms 12244 KB First line is correct, but the reconstruction is not.
8 Partially correct 7 ms 12292 KB First line is correct, but the reconstruction is not.
9 Correct 7 ms 12244 KB Correct.
10 Correct 7 ms 12244 KB Correct.
11 Correct 7 ms 12244 KB Correct.
12 Partially correct 7 ms 12244 KB First line is correct, but the reconstruction is not.
13 Correct 6 ms 12244 KB Correct.
14 Correct 7 ms 12204 KB Correct.
15 Correct 7 ms 12244 KB Correct.
16 Correct 7 ms 12224 KB Correct.
17 Correct 7 ms 12244 KB Correct.
18 Correct 6 ms 12244 KB Correct.
19 Correct 7 ms 12244 KB Correct.
20 Correct 7 ms 12192 KB Correct.
21 Correct 7 ms 12244 KB Correct.
22 Correct 7 ms 12260 KB Correct.
23 Correct 7 ms 12304 KB Correct.
24 Correct 7 ms 13472 KB Correct.
25 Partially correct 7 ms 13112 KB First line is correct, but the reconstruction is not.
26 Partially correct 8 ms 13780 KB First line is correct, but the reconstruction is not.
27 Partially correct 8 ms 13012 KB First line is correct, but the reconstruction is not.
28 Partially correct 7 ms 13012 KB First line is correct, but the reconstruction is not.
29 Partially correct 7 ms 12628 KB First line is correct, but the reconstruction is not.
30 Partially correct 7 ms 12628 KB First line is correct, but the reconstruction is not.
31 Partially correct 7 ms 13160 KB First line is correct, but the reconstruction is not.
32 Partially correct 9 ms 14588 KB First line is correct, but the reconstruction is not.
33 Partially correct 9 ms 14548 KB First line is correct, but the reconstruction is not.
34 Partially correct 9 ms 14548 KB First line is correct, but the reconstruction is not.
35 Partially correct 10 ms 14548 KB First line is correct, but the reconstruction is not.
36 Partially correct 8 ms 14576 KB First line is correct, but the reconstruction is not.
37 Partially correct 9 ms 14620 KB First line is correct, but the reconstruction is not.
38 Partially correct 8 ms 14620 KB First line is correct, but the reconstruction is not.
39 Partially correct 9 ms 14552 KB First line is correct, but the reconstruction is not.
40 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
41 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
42 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
43 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
44 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
45 Partially correct 8 ms 14548 KB First line is correct, but the reconstruction is not.
46 Partially correct 10 ms 14572 KB First line is correct, but the reconstruction is not.
47 Partially correct 8 ms 14588 KB First line is correct, but the reconstruction is not.
48 Partially correct 8 ms 14584 KB First line is correct, but the reconstruction is not.
49 Partially correct 9 ms 14548 KB First line is correct, but the reconstruction is not.
50 Partially correct 40 ms 19808 KB First line is correct, but the reconstruction is not.
51 Partially correct 77 ms 17468 KB First line is correct, but the reconstruction is not.
52 Partially correct 63 ms 20496 KB First line is correct, but the reconstruction is not.
53 Partially correct 39 ms 20024 KB First line is correct, but the reconstruction is not.
54 Partially correct 54 ms 19416 KB First line is correct, but the reconstruction is not.
55 Partially correct 51 ms 20824 KB First line is correct, but the reconstruction is not.
56 Partially correct 40 ms 20284 KB First line is correct, but the reconstruction is not.
57 Partially correct 37 ms 20152 KB First line is correct, but the reconstruction is not.
58 Partially correct 62 ms 17408 KB First line is correct, but the reconstruction is not.
59 Partially correct 41 ms 19500 KB First line is correct, but the reconstruction is not.
60 Partially correct 50 ms 20336 KB First line is correct, but the reconstruction is not.
61 Partially correct 65 ms 19160 KB First line is correct, but the reconstruction is not.
62 Partially correct 48 ms 20220 KB First line is correct, but the reconstruction is not.
63 Partially correct 47 ms 20464 KB First line is correct, but the reconstruction is not.
64 Partially correct 17 ms 16596 KB First line is correct, but the reconstruction is not.
65 Partially correct 50 ms 20400 KB First line is correct, but the reconstruction is not.
66 Partially correct 63 ms 19564 KB First line is correct, but the reconstruction is not.
67 Partially correct 72 ms 19988 KB First line is correct, but the reconstruction is not.
68 Partially correct 59 ms 20820 KB First line is correct, but the reconstruction is not.
69 Partially correct 49 ms 20116 KB First line is correct, but the reconstruction is not.
70 Partially correct 46 ms 20208 KB First line is correct, but the reconstruction is not.
71 Partially correct 58 ms 20852 KB First line is correct, but the reconstruction is not.
72 Partially correct 45 ms 20816 KB First line is correct, but the reconstruction is not.
73 Partially correct 57 ms 21108 KB First line is correct, but the reconstruction is not.
74 Partially correct 74 ms 20756 KB First line is correct, but the reconstruction is not.
75 Partially correct 70 ms 21296 KB First line is correct, but the reconstruction is not.