oj.uz

Submission #853128

# Submission time Handle Problem Language Result Execution time Memory
853128 2023-09-23T13:05:03 Z vjudge1 Skandi (COCI20_skandi) C++17
110 / 110
 4850 ms 79120 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 15 ms 64344 KB Correct.
2 Correct 16 ms 64344 KB Correct.
3 Correct 15 ms 64348 KB Correct.
4 Correct 16 ms 64344 KB Correct.
5 Correct 15 ms 64344 KB Correct.
6 Correct 15 ms 64344 KB Correct.
7 Correct 18 ms 64344 KB Correct.
8 Correct 17 ms 64344 KB Correct.
9 Correct 15 ms 64344 KB Correct.
10 Correct 16 ms 64344 KB Correct.
11 Correct 16 ms 64344 KB Correct.
12 Correct 16 ms 64344 KB Correct.
13 Correct 15 ms 64344 KB Correct.
14 Correct 16 ms 64508 KB Correct.
15 Correct 15 ms 64344 KB Correct.
16 Correct 16 ms 64344 KB Correct.
17 Correct 15 ms 64344 KB Correct.
18 Correct 18 ms 64344 KB Correct.
19 Correct 15 ms 64344 KB Correct.
20 Correct 17 ms 64348 KB Correct.
21 Correct 16 ms 64348 KB Correct.
22 Correct 16 ms 64344 KB Correct.
23 Correct 17 ms 64600 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 64348 KB Correct.
2 Correct 56 ms 64364 KB Correct.
3 Correct 68 ms 64456 KB Correct.
4 Correct 30 ms 64344 KB Correct.
5 Correct 46 ms 64352 KB Correct.
6 Correct 28 ms 64344 KB Correct.
7 Correct 29 ms 64304 KB Correct.
8 Correct 55 ms 64344 KB Correct.
9 Correct 176 ms 64512 KB Correct.
10 Correct 99 ms 64592 KB Correct.
11 Correct 115 ms 64620 KB Correct.
12 Correct 157 ms 64560 KB Correct.
13 Correct 159 ms 64552 KB Correct.
14 Correct 129 ms 64560 KB Correct.
15 Correct 134 ms 64592 KB Correct.
16 Correct 152 ms 64592 KB Correct.
17 Correct 160 ms 64556 KB Correct.
18 Correct 143 ms 64592 KB Correct.
19 Correct 132 ms 64592 KB Correct.
20 Correct 153 ms 64592 KB Correct.
21 Correct 144 ms 64564 KB Correct.
22 Correct 133 ms 64592 KB Correct.
23 Correct 127 ms 64592 KB Correct.
24 Correct 164 ms 64552 KB Correct.
25 Correct 141 ms 64592 KB Correct.
26 Correct 154 ms 64628 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 64344 KB Correct.
2 Correct 16 ms 64344 KB Correct.
3 Correct 15 ms 64348 KB Correct.
4 Correct 16 ms 64344 KB Correct.
5 Correct 15 ms 64344 KB Correct.
6 Correct 15 ms 64344 KB Correct.
7 Correct 18 ms 64344 KB Correct.
8 Correct 17 ms 64344 KB Correct.
9 Correct 15 ms 64344 KB Correct.
10 Correct 16 ms 64344 KB Correct.
11 Correct 16 ms 64344 KB Correct.
12 Correct 16 ms 64344 KB Correct.
13 Correct 15 ms 64344 KB Correct.
14 Correct 16 ms 64508 KB Correct.
15 Correct 15 ms 64344 KB Correct.
16 Correct 16 ms 64344 KB Correct.
17 Correct 15 ms 64344 KB Correct.
18 Correct 18 ms 64344 KB Correct.
19 Correct 15 ms 64344 KB Correct.
20 Correct 17 ms 64348 KB Correct.
21 Correct 16 ms 64348 KB Correct.
22 Correct 16 ms 64344 KB Correct.
23 Correct 17 ms 64600 KB Correct.
24 Correct 34 ms 64348 KB Correct.
25 Correct 56 ms 64364 KB Correct.
26 Correct 68 ms 64456 KB Correct.
27 Correct 30 ms 64344 KB Correct.
28 Correct 46 ms 64352 KB Correct.
29 Correct 28 ms 64344 KB Correct.
30 Correct 29 ms 64304 KB Correct.
31 Correct 55 ms 64344 KB Correct.
32 Correct 176 ms 64512 KB Correct.
33 Correct 99 ms 64592 KB Correct.
34 Correct 115 ms 64620 KB Correct.
35 Correct 157 ms 64560 KB Correct.
36 Correct 159 ms 64552 KB Correct.
37 Correct 129 ms 64560 KB Correct.
38 Correct 134 ms 64592 KB Correct.
39 Correct 152 ms 64592 KB Correct.
40 Correct 160 ms 64556 KB Correct.
41 Correct 143 ms 64592 KB Correct.
42 Correct 132 ms 64592 KB Correct.
43 Correct 153 ms 64592 KB Correct.
44 Correct 144 ms 64564 KB Correct.
45 Correct 133 ms 64592 KB Correct.
46 Correct 127 ms 64592 KB Correct.
47 Correct 164 ms 64552 KB Correct.
48 Correct 141 ms 64592 KB Correct.
49 Correct 154 ms 64628 KB Correct.
50 Correct 3953 ms 76072 KB Correct.
51 Correct 1334 ms 71608 KB Correct.
52 Correct 4484 ms 77748 KB Correct.
53 Correct 4075 ms 76036 KB Correct.
54 Correct 4323 ms 75960 KB Correct.
55 Correct 4813 ms 78044 KB Correct.
56 Correct 3968 ms 76848 KB Correct.
57 Correct 3812 ms 76700 KB Correct.
58 Correct 1151 ms 71248 KB Correct.
59 Correct 3743 ms 75436 KB Correct.
60 Correct 4379 ms 77052 KB Correct.
61 Correct 3094 ms 74892 KB Correct.
62 Correct 4315 ms 77192 KB Correct.
63 Correct 4345 ms 77152 KB Correct.
64 Correct 146 ms 69176 KB Correct.
65 Correct 4296 ms 77036 KB Correct.
66 Correct 3633 ms 76204 KB Correct.
67 Correct 3767 ms 76880 KB Correct.
68 Correct 4850 ms 78204 KB Correct.
69 Correct 4123 ms 76740 KB Correct.
70 Correct 4099 ms 76816 KB Correct.
71 Correct 4651 ms 78468 KB Correct.
72 Correct 4133 ms 77780 KB Correct.
73 Correct 4773 ms 78864 KB Correct.
74 Correct 4308 ms 78416 KB Correct.
75 Correct 4838 ms 79120 KB Correct.