답안 #570648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570648	2022-05-30T22:38:37 Z	NekoRolly	Skandi (COCI20_skandi)	C++17	55 / 110	77 ms	21296 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]) 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

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

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

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

답안 #570648

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