답안 #570655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570655	2022-05-30T23:28:49 Z	NekoRolly	Skandi (COCI20_skandi)	C++17	55 / 110	72 ms	13160 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";
		ans--;
	}

	while (ans != 0) ans = ans;

    return 0;
}

Subtask #1
9.0 / 18.0

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

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

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

답안 #570655

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