답안 #570651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570651	2022-05-30T22:44:20 Z	NekoRolly	Skandi (COCI20_skandi)	C++17	55 / 110	92 ms	21304 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],_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] && i == _v[_u[i]]) for (int v : adj[i])
		if (!_v[v] || v != _u[_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] && i == _u[_v[i]] && !vis[i])
		cout << posL[i].first+1 << " " << posL[i].second << " DESNO\n";

    return 0;
}

Subtask #1
9.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	12244 KB	Correct.
2	Correct	7 ms	12244 KB	Correct.
3	Correct	8 ms	12244 KB	Correct.
4	Correct	8 ms	12244 KB	Correct.
5	Correct	8 ms	12240 KB	Correct.
6	Correct	6 ms	12244 KB	Correct.
7	Partially correct	6 ms	12244 KB	First line is correct, but the reconstruction is not.
8	Partially correct	6 ms	12316 KB	First line is correct, but the reconstruction is not.
9	Correct	6 ms	12244 KB	Correct.
10	Correct	6 ms	12244 KB	Correct.
11	Correct	6 ms	12244 KB	Correct.
12	Partially correct	7 ms	12252 KB	First line is correct, but the reconstruction is not.
13	Correct	7 ms	12220 KB	Correct.
14	Correct	7 ms	12244 KB	Correct.
15	Correct	8 ms	12244 KB	Correct.
16	Correct	8 ms	12244 KB	Correct.
17	Correct	9 ms	12220 KB	Correct.
18	Correct	6 ms	12248 KB	Correct.
19	Correct	6 ms	12244 KB	Correct.
20	Correct	7 ms	12244 KB	Correct.
21	Correct	7 ms	12244 KB	Correct.
22	Correct	6 ms	12244 KB	Correct.
23	Correct	6 ms	12308 KB	Correct.

Subtask #2
16.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	13524 KB	Correct.
2	Partially correct	6 ms	13140 KB	First line is correct, but the reconstruction is not.
3	Partially correct	7 ms	13792 KB	First line is correct, but the reconstruction is not.
4	Partially correct	7 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	12616 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	8 ms	13084 KB	First line is correct, but the reconstruction is not.
9	Partially correct	11 ms	14548 KB	First line is correct, but the reconstruction is not.
10	Partially correct	11 ms	14612 KB	First line is correct, but the reconstruction is not.
11	Partially correct	9 ms	14632 KB	First line is correct, but the reconstruction is not.
12	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
13	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
14	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
15	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
16	Partially correct	8 ms	14548 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	10 ms	14604 KB	First line is correct, but the reconstruction is not.
19	Partially correct	10 ms	14636 KB	First line is correct, but the reconstruction is not.
20	Partially correct	10 ms	14608 KB	First line is correct, but the reconstruction is not.
21	Partially correct	9 ms	14548 KB	First line is correct, but the reconstruction is not.
22	Partially correct	9 ms	14548 KB	First line is correct, but the reconstruction is not.
23	Partially correct	11 ms	14592 KB	First line is correct, but the reconstruction is not.
24	Partially correct	9 ms	14616 KB	First line is correct, but the reconstruction is not.
25	Partially correct	9 ms	14548 KB	First line is correct, but the reconstruction is not.
26	Partially correct	8 ms	14524 KB	First line is correct, but the reconstruction is not.

Subtask #3
30.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	12244 KB	Correct.
2	Correct	7 ms	12244 KB	Correct.
3	Correct	8 ms	12244 KB	Correct.
4	Correct	8 ms	12244 KB	Correct.
5	Correct	8 ms	12240 KB	Correct.
6	Correct	6 ms	12244 KB	Correct.
7	Partially correct	6 ms	12244 KB	First line is correct, but the reconstruction is not.
8	Partially correct	6 ms	12316 KB	First line is correct, but the reconstruction is not.
9	Correct	6 ms	12244 KB	Correct.
10	Correct	6 ms	12244 KB	Correct.
11	Correct	6 ms	12244 KB	Correct.
12	Partially correct	7 ms	12252 KB	First line is correct, but the reconstruction is not.
13	Correct	7 ms	12220 KB	Correct.
14	Correct	7 ms	12244 KB	Correct.
15	Correct	8 ms	12244 KB	Correct.
16	Correct	8 ms	12244 KB	Correct.
17	Correct	9 ms	12220 KB	Correct.
18	Correct	6 ms	12248 KB	Correct.
19	Correct	6 ms	12244 KB	Correct.
20	Correct	7 ms	12244 KB	Correct.
21	Correct	7 ms	12244 KB	Correct.
22	Correct	6 ms	12244 KB	Correct.
23	Correct	6 ms	12308 KB	Correct.
24	Correct	8 ms	13524 KB	Correct.
25	Partially correct	6 ms	13140 KB	First line is correct, but the reconstruction is not.
26	Partially correct	7 ms	13792 KB	First line is correct, but the reconstruction is not.
27	Partially correct	7 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	12616 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	8 ms	13084 KB	First line is correct, but the reconstruction is not.
32	Partially correct	11 ms	14548 KB	First line is correct, but the reconstruction is not.
33	Partially correct	11 ms	14612 KB	First line is correct, but the reconstruction is not.
34	Partially correct	9 ms	14632 KB	First line is correct, but the reconstruction is not.
35	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
36	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
37	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
38	Partially correct	8 ms	14548 KB	First line is correct, but the reconstruction is not.
39	Partially correct	8 ms	14548 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	10 ms	14604 KB	First line is correct, but the reconstruction is not.
42	Partially correct	10 ms	14636 KB	First line is correct, but the reconstruction is not.
43	Partially correct	10 ms	14608 KB	First line is correct, but the reconstruction is not.
44	Partially correct	9 ms	14548 KB	First line is correct, but the reconstruction is not.
45	Partially correct	9 ms	14548 KB	First line is correct, but the reconstruction is not.
46	Partially correct	11 ms	14592 KB	First line is correct, but the reconstruction is not.
47	Partially correct	9 ms	14616 KB	First line is correct, but the reconstruction is not.
48	Partially correct	9 ms	14548 KB	First line is correct, but the reconstruction is not.
49	Partially correct	8 ms	14524 KB	First line is correct, but the reconstruction is not.
50	Partially correct	39 ms	19788 KB	First line is correct, but the reconstruction is not.
51	Partially correct	84 ms	17452 KB	First line is correct, but the reconstruction is not.
52	Partially correct	92 ms	20396 KB	First line is correct, but the reconstruction is not.
53	Partially correct	45 ms	20044 KB	First line is correct, but the reconstruction is not.
54	Partially correct	61 ms	19348 KB	First line is correct, but the reconstruction is not.
55	Partially correct	53 ms	20732 KB	First line is correct, but the reconstruction is not.
56	Partially correct	44 ms	20300 KB	First line is correct, but the reconstruction is not.
57	Partially correct	45 ms	20172 KB	First line is correct, but the reconstruction is not.
58	Partially correct	80 ms	17400 KB	First line is correct, but the reconstruction is not.
59	Partially correct	38 ms	19484 KB	First line is correct, but the reconstruction is not.
60	Partially correct	49 ms	20344 KB	First line is correct, but the reconstruction is not.
61	Partially correct	57 ms	19148 KB	First line is correct, but the reconstruction is not.
62	Partially correct	49 ms	20224 KB	First line is correct, but the reconstruction is not.
63	Partially correct	48 ms	20460 KB	First line is correct, but the reconstruction is not.
64	Partially correct	16 ms	16596 KB	First line is correct, but the reconstruction is not.
65	Partially correct	51 ms	20420 KB	First line is correct, but the reconstruction is not.
66	Partially correct	65 ms	19492 KB	First line is correct, but the reconstruction is not.
67	Partially correct	78 ms	19996 KB	First line is correct, but the reconstruction is not.
68	Partially correct	49 ms	20812 KB	First line is correct, but the reconstruction is not.
69	Partially correct	45 ms	20108 KB	First line is correct, but the reconstruction is not.
70	Partially correct	49 ms	20272 KB	First line is correct, but the reconstruction is not.
71	Partially correct	60 ms	20908 KB	First line is correct, but the reconstruction is not.
72	Partially correct	56 ms	20752 KB	First line is correct, but the reconstruction is not.
73	Partially correct	68 ms	21140 KB	First line is correct, but the reconstruction is not.
74	Partially correct	83 ms	20708 KB	First line is correct, but the reconstruction is not.
75	Partially correct	76 ms	21304 KB	First line is correct, but the reconstruction is not.

답안 #570651

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