답안 #570654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570654	2022-05-30T23:27:05 Z	NekoRolly	Skandi (COCI20_skandi)	C++17	55 / 110	78 ms	13132 KB

skandi

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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.

답안 #570654

Compilation message

Subtask #1 9.0 / 18.0

Subtask #2 16.0 / 32.0

Subtask #3 30.0 / 60.0

Subtask #1
9.0 / 18.0

Subtask #2
16.0 / 32.0

Subtask #3
30.0 / 60.0