oj.uz

Submission #853134

# Submission time Handle Problem Language Result Execution time Memory
853134 2023-09-23T13:12:22 Z Onur_Ilgaz Skandi (COCI20_skandi) C++17
110 / 110
 4791 ms 78676 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 505
using namespace std;
const int MX = N * N;
vector <vector<int> > adj(MX * 4), cover(MX * 4);
vector <int> match(MX * 4), vis;

int get(int x, int y) {
	return x * N + y;
}

pair<int, int> reget(int val) {
	if(val > MX) val -= MX;
	return {val / N, val % N};
}

void printp(pair<int,int> a) {
	cout<<a.first<<" "<<a.second<<"\n";
}

bool aug(int node) {
	if(vis[node]) return 0;
	vis[node] = 1;
	for(auto it:adj[node]) {
		if(!match[it] or aug(match[it])) {
			match[it] = node;
			return 1;
		}
	}
	return 0;
}

void solve(set <int> &left, set <int> &right) {
	int ans = 0;
	// ilk önce random greedy matching yap
	for(auto it:left) {
		vector <int> availableNodes;
		for(auto itt:adj[it])
			if(!match[itt]) {
				availableNodes.push_back(itt);
			}

		if(availableNodes.size() == 0) {
			continue;
		}

		ans++;
		int select = availableNodes[rand() % (int)availableNodes.size()];
		match[select] = it;
		match[it] = it;
	}
	for(auto it:left) {
		if(match[it]) continue;
		vis.assign(MX * 4, 0);
		ans += aug(it);
	}
	cout<<ans<<"\n";
	set <int> bnodes = left;
	// build a better adj table
	for(auto it:right) {
		if(match[it]) {
			bnodes.erase(match[it]);
		}
	}
	queue<int> nodes;
	for(auto it:bnodes) {
		nodes.push(it);
	}

	// for every single non-matched left node start a bfs
	vis.assign(MX * 4, 0);
	while(!nodes.empty()) {
		int node = nodes.front();
		nodes.pop();
		vis[node] = 1;
		for(auto it:adj[node]) {
			if(!vis[it] and match[it] != node) {
				vis[it] = 1;
				vis[match[it]] = 1;
				nodes.push(match[it]);
			}
		}
	}

	// get the juice
	for(auto it:left) {
		if(!vis[it]) {
			cout<<(reget(it).first + 1)<<" "<<(reget(it).second + 1)<<" DESNO\n";
		}
	}
	for(auto it:right) {
		if(vis[it]) {
			cout<<(reget(it).first + 1)<<" "<<(reget(it).second + 1)<<" DOLJE\n";
		}
	}

}

int32_t main(){
	fast
	int n, m;
	cin>>n>>m;
	vector <string> s(n);
	for(int i = 0; i < n; i++) {
		cin>>s[i];
	}
	vector <int> col(m); // last bit in this column
	set <int> lnodes, rnodes;
	for(int i = 1; i < n; i++) {
		int prev = 0;
		for(int j = 1; j < m; j++) {
			if(s[i][j] == '1') { 
				col[j] = i;
				prev = j;
			}
			else {
				adj[get(col[j], j)].push_back(MX + get(i, prev));
				adj[MX + get(i, prev)].push_back(get(col[j], j));
				lnodes.insert(MX + get(i, prev));
				rnodes.insert(get(col[j], j));
			}
		}
	}
	solve(lnodes, rnodes);
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 64344 KB Correct.
2 Correct 16 ms 64344 KB Correct.
3 Correct 15 ms 64344 KB Correct.
4 Correct 16 ms 64348 KB Correct.
5 Correct 15 ms 64344 KB Correct.
6 Correct 15 ms 64344 KB Correct.
7 Correct 15 ms 64344 KB Correct.
8 Correct 15 ms 64348 KB Correct.
9 Correct 18 ms 64344 KB Correct.
10 Correct 16 ms 64344 KB Correct.
11 Correct 15 ms 64344 KB Correct.
12 Correct 17 ms 64348 KB Correct.
13 Correct 14 ms 64344 KB Correct.
14 Correct 15 ms 64344 KB Correct.
15 Correct 16 ms 64352 KB Correct.
16 Correct 16 ms 64344 KB Correct.
17 Correct 15 ms 64344 KB Correct.
18 Correct 16 ms 64344 KB Correct.
19 Correct 16 ms 64344 KB Correct.
20 Correct 16 ms 64344 KB Correct.
21 Correct 14 ms 64504 KB Correct.
22 Correct 16 ms 64344 KB Correct.
23 Correct 15 ms 64344 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 64344 KB Correct.
2 Correct 57 ms 64344 KB Correct.
3 Correct 51 ms 64344 KB Correct.
4 Correct 30 ms 64344 KB Correct.
5 Correct 56 ms 64596 KB Correct.
6 Correct 28 ms 64344 KB Correct.
7 Correct 28 ms 64344 KB Correct.
8 Correct 53 ms 64344 KB Correct.
9 Correct 180 ms 64504 KB Correct.
10 Correct 115 ms 64544 KB Correct.
11 Correct 117 ms 64560 KB Correct.
12 Correct 153 ms 64596 KB Correct.
13 Correct 125 ms 64592 KB Correct.
14 Correct 131 ms 64572 KB Correct.
15 Correct 142 ms 64552 KB Correct.
16 Correct 145 ms 64556 KB Correct.
17 Correct 143 ms 64596 KB Correct.
18 Correct 139 ms 64592 KB Correct.
19 Correct 129 ms 64592 KB Correct.
20 Correct 141 ms 64540 KB Correct.
21 Correct 149 ms 64592 KB Correct.
22 Correct 129 ms 64592 KB Correct.
23 Correct 126 ms 64592 KB Correct.
24 Correct 148 ms 64344 KB Correct.
25 Correct 135 ms 64556 KB Correct.
26 Correct 133 ms 64596 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 64344 KB Correct.
2 Correct 16 ms 64344 KB Correct.
3 Correct 15 ms 64344 KB Correct.
4 Correct 16 ms 64348 KB Correct.
5 Correct 15 ms 64344 KB Correct.
6 Correct 15 ms 64344 KB Correct.
7 Correct 15 ms 64344 KB Correct.
8 Correct 15 ms 64348 KB Correct.
9 Correct 18 ms 64344 KB Correct.
10 Correct 16 ms 64344 KB Correct.
11 Correct 15 ms 64344 KB Correct.
12 Correct 17 ms 64348 KB Correct.
13 Correct 14 ms 64344 KB Correct.
14 Correct 15 ms 64344 KB Correct.
15 Correct 16 ms 64352 KB Correct.
16 Correct 16 ms 64344 KB Correct.
17 Correct 15 ms 64344 KB Correct.
18 Correct 16 ms 64344 KB Correct.
19 Correct 16 ms 64344 KB Correct.
20 Correct 16 ms 64344 KB Correct.
21 Correct 14 ms 64504 KB Correct.
22 Correct 16 ms 64344 KB Correct.
23 Correct 15 ms 64344 KB Correct.
24 Correct 35 ms 64344 KB Correct.
25 Correct 57 ms 64344 KB Correct.
26 Correct 51 ms 64344 KB Correct.
27 Correct 30 ms 64344 KB Correct.
28 Correct 56 ms 64596 KB Correct.
29 Correct 28 ms 64344 KB Correct.
30 Correct 28 ms 64344 KB Correct.
31 Correct 53 ms 64344 KB Correct.
32 Correct 180 ms 64504 KB Correct.
33 Correct 115 ms 64544 KB Correct.
34 Correct 117 ms 64560 KB Correct.
35 Correct 153 ms 64596 KB Correct.
36 Correct 125 ms 64592 KB Correct.
37 Correct 131 ms 64572 KB Correct.
38 Correct 142 ms 64552 KB Correct.
39 Correct 145 ms 64556 KB Correct.
40 Correct 143 ms 64596 KB Correct.
41 Correct 139 ms 64592 KB Correct.
42 Correct 129 ms 64592 KB Correct.
43 Correct 141 ms 64540 KB Correct.
44 Correct 149 ms 64592 KB Correct.
45 Correct 129 ms 64592 KB Correct.
46 Correct 126 ms 64592 KB Correct.
47 Correct 148 ms 64344 KB Correct.
48 Correct 135 ms 64556 KB Correct.
49 Correct 133 ms 64596 KB Correct.
50 Correct 3698 ms 75868 KB Correct.
51 Correct 1331 ms 71500 KB Correct.
52 Correct 4233 ms 77520 KB Correct.
53 Correct 3638 ms 76048 KB Correct.
54 Correct 3775 ms 75644 KB Correct.
55 Correct 4545 ms 77904 KB Correct.
56 Correct 3943 ms 76616 KB Correct.
57 Correct 3926 ms 76468 KB Correct.
58 Correct 1108 ms 71012 KB Correct.
59 Correct 3840 ms 75200 KB Correct.
60 Correct 4307 ms 76832 KB Correct.
61 Correct 2977 ms 74640 KB Correct.
62 Correct 4291 ms 76976 KB Correct.
63 Correct 4251 ms 76932 KB Correct.
64 Correct 118 ms 68944 KB Correct.
65 Correct 4073 ms 76880 KB Correct.
66 Correct 3587 ms 76256 KB Correct.
67 Correct 3432 ms 76616 KB Correct.
68 Correct 4665 ms 77972 KB Correct.
69 Correct 4040 ms 76516 KB Correct.
70 Correct 4051 ms 76596 KB Correct.
71 Correct 4518 ms 78196 KB Correct.
72 Correct 4070 ms 77732 KB Correct.
73 Correct 4718 ms 78616 KB Correct.
74 Correct 4349 ms 77996 KB Correct.
75 Correct 4791 ms 78676 KB Correct.