Submission #1214068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214068		ericl23302	Simurgh (IOI17_simurgh)	C++20	19 / 100	94 ms	7088 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

void setDsu(vector<int> &dsu, vector<int> &sz) {
	int n = dsu.size();
	for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1;
}

int findHead(vector<int> &dsu, int node) {
	if (node == dsu[node]) return node;
	return dsu[node] = findHead(dsu, dsu[node]);
}

bool merge(vector<int> &dsu, vector<int> &sz, int a, int b) {
	a = findHead(dsu, a);
	b = findHead(dsu, b);
	if (a == b) return false;
	if (sz[a] < sz[b]) swap(a, b);
	dsu[b] = a;
	sz[a] += sz[b];
	return true;
}

void dfs(vector<vector<pair<int, int>>> &adjacency, vector<int> &dfsSequence, vector<int> &parent, vector<bool> &dfsVisited, int curNode) {
	for (auto &[i, index] : adjacency[curNode])	{
		if (dfsVisited[i]) continue;
		dfsVisited[i] = true;
		dfsSequence.push_back(i);
		parent[i] = curNode;
		dfs(adjacency, dfsSequence, parent, dfsVisited, i);
	}
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	if (n == 2) return {0};
	int m = u.size();
	vector<vector<pair<int, int>>> adjacency(n);
	vector<vector<int>> adjacencyMatrix(n, vector<int>(n, -1));
	for (int i = 0; i < m; ++i) {
		adjacency[u[i]].emplace_back(v[i], i);
		adjacency[v[i]].emplace_back(u[i], i);
		adjacencyMatrix[u[i]][v[i]] = i;
		adjacencyMatrix[v[i]][u[i]] = i;
	}

	// cout << "Find roads Begins" << endl;

	vector<pair<int, int>> t;
	vector<bool> dfsVisited(n, false), tCounted(n, false);
	vector<int> parent(n, -1), dfsSequence;
	vector<vector<int>> ears;

	dfs(adjacency, dfsSequence, parent, dfsVisited, 0);

	// cout << "DFS complete" << endl;

	vector<int> dsu(n), sz(n);
	vector<vector<int>> inTree(n, vector<int>(n, -1));
	setDsu(dsu, sz);

	// cout << "Sequence: ";
	// for (int &i : dfsSequence) cout << i << ' ';
	// cout << endl;

	for (int &u : dfsSequence) {
		for (auto &[v, index] : adjacency[u]) {
			if (parent[u] == v || parent[v] == u) continue;
			vector<int> ear;
			bool add = false;
			ear.push_back(u);
			if (!tCounted[u]) add = true, tCounted[u] = true;
			for (int x = v; ; x = parent[x]) {
				if (x == ear[0]) break;
				ear.push_back(x);
				if (merge(dsu, sz, x, parent[x])) inTree[x][parent[x]] = t.size(), inTree[parent[x]][x] = t.size(), t.emplace_back(x, parent[x]);
				if (tCounted[x]) break;
				add = true;
				tCounted[x] = true;
			}
			// for (int &i : ear) cout << i << ' ';
			// cout << "add: " << add << endl;
			if (add) ears.push_back(ear);
		}
	}
	
	vector<int> edgeStates(m, -1); // -1 = unknown, 0 = not golden, 1 = golden
	vector<int> res;
	vector<int> tWeight(n - 1, 0);
	vector<vector<bool>> goldTree(n, vector<bool>(n, false));
	vector<int> sub(n, 0);

	// cout << "t: " << t.size() << endl;
	// for (auto &i : t) cout << i.first << ' ' << i.second << "   ";
	// cout << endl;
	
	for (int i = 0; i < m; ++i) {
		if (merge(dsu, sz, u[i], v[i])) {
			inTree[u[i]][v[i]] = t.size();
			inTree[v[i]][u[i]] = t.size();
			t.emplace_back(u[i], v[i]);
			int which = t.size() - 1;
			tWeight[which] = 1;
			res.push_back(adjacencyMatrix[t[which].first][t[which].second]);
			++sub[t[which].first];
			++sub[t[which].second];
			goldTree[t[which].first][t[which].second] = true;
			goldTree[t[which].second][t[which].first] = true;
		}
	}
	
	// cout << "t: " << t.size() << endl;
	// for (auto &i : t) cout << i.first << ' ' << i.second << "   ";
	// cout << endl;

	// cout << "res: " << res.size() << endl;
	// for (auto &i : res) cout << u[i] << ' ' << v[i] << "   ";
	// cout << endl;
	
	assert(t.size() == n - 1);
	// cout << "Tree chosen" << endl;

	for (auto &ear : ears) {
		int earSz = ear.size();
		int known = -1;
		bool knownIs = false;
		vector<pair<int, int>> curCycle;
		for (int i = 0; i < earSz - 1; ++i) curCycle.emplace_back(ear[i], ear[i + 1]);
		if (earSz > 2) curCycle.emplace_back(ear[earSz - 1], ear[0]);

		int cycleSz = curCycle.size();
		for (int i = 0; i < cycleSz; ++i) {
			if (edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] != -1) {
				known = i;
				knownIs = edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]];
				break;
			}
		}

		vector<int> records(cycleSz, -1);
		int sample = 0;
		for (int i = 0; i < cycleSz; ++i) {
			if (known != -1 && (inTree[curCycle[i].first][curCycle[i].second] == -1 || edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] != -1) && i != known) continue;
			++sample;
			vector<int> r;
			setDsu(dsu, sz);
			// cout << "NEW" << endl;
			for (int j = 0; j < cycleSz; ++j) {
				// cout << curCycle[j].first << ' ' << curCycle[j].second << endl; 
				if (i == j) continue;
				assert(merge(dsu, sz, curCycle[j].first, curCycle[j].second));
				r.push_back(adjacencyMatrix[curCycle[j].first][curCycle[j].second]);
			}
			for (auto &[a, b] : t) {
				if (merge(dsu, sz, a, b)) r.push_back(adjacencyMatrix[a][b]);
			}
			assert(r.size() == n - 1);
			records[i] = count_common_roads(r);
		}
		
		if (sample < 2) continue;

		if (known == -1) {
			int least = records[0], most = records[0];
			for (int &j : records) {
				if (j == -1) continue;
				least = min(least, j), most = max(most, j);
			}

			for (int i = 0; i < cycleSz; ++i) {
				if (records[i] == -1) continue;
				if (records[i] != most) {
					edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 1;
					if (inTree[curCycle[i].first][curCycle[i].second] != -1) {
						int which = inTree[curCycle[i].first][curCycle[i].second];
						tWeight[which] = 1;
						res.push_back(adjacencyMatrix[t[which].first][t[which].second]);
						++sub[t[which].first];
						++sub[t[which].second];
						goldTree[t[which].first][t[which].second] = true;
						goldTree[t[which].second][t[which].first] = true;
					} 
					// cout << "FOUND GOLD EDGE(Unknown): " << i << ' ' << curCycle[i].first << ' ' << curCycle[i].second << '\n';
				} else edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 0;
			}
		} else {
			for (int i = 0; i < cycleSz; ++i) {
				if (records[i] == -1 || i == known) continue;
				if ((records[i] == records[known] && knownIs) || (records[i] != records[known] && !knownIs)) {
					edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 1;
					if (inTree[curCycle[i].first][curCycle[i].second] != -1) {
						int which = inTree[curCycle[i].first][curCycle[i].second];
						tWeight[which] = 1;
						res.push_back(adjacencyMatrix[curCycle[i].first][curCycle[i].second]);
						++sub[t[which].first];
						++sub[t[which].second];
						goldTree[t[which].first][t[which].second] = true;
						goldTree[t[which].second][t[which].first] = true;
					}

					// cout << "FOUND GOLD EDGE(Known): " << i << ' ' << curCycle[i].first << ' ' << curCycle[i].second << '\n';
					// cout << "KNOWN EDGE IS: " << known << ' ' << curCycle[known].first << ' ' << curCycle[known].second << ' ' << knownIs << '\n';
				} else edgeStates[adjacencyMatrix[curCycle[i].first][curCycle[i].second]] = 0;
			}
		}

		// for (int &i : ear) cout << i << ' ';
		// cout << endl;
		// for (int i = 0; i < m; ++i) cout << u[i] << ' ' << v[i] << ' ' << edgeStates[i] << "   ";
		// cout << endl;
	}

	// cout << "res: " << res.size() << endl;
	// for (auto &i : res) cout << u[i] << ' ' << v[i] << "   ";
	// cout << endl;

	// cout << "Edges of Tree done" << endl;

	/*
	// vector<int> res;
	// vector<int> tWeight(n - 1, 0);
	// vector<vector<bool>> goldTree(n, vector<bool>(n, false));
	// vector<int> sub(n, 0);
	// for (int i = 0; i < n - 1; ++i) {
	// 	vector<pair<int, int>> curCycle = {t[i]};
	// 	int other = 0;
	// 	if (t[i].first == 0 || t[i].second == 0) {
	// 		other = 1;
	// 		if (t[i].first == 1 || t[i].second == 1) other = 2;
	// 	}
	// 	curCycle.emplace_back(t[i].first, other);
	// 	curCycle.emplace_back(t[i].second, other);

	// 	vector<int> scores;
	// 	for (int j = 0; j < 3; ++j) {
	// 		vector<int> r;
	// 		setDsu(dsu, sz);
	// 		for (int k = 0; k < 3; ++k) {
	// 			if (j == k) continue;
	// 			assert(merge(dsu, sz, curCycle[k].first, curCycle[k].second));
	// 			r.push_back(adjacencyMatrix[curCycle[k].first][curCycle[k].second]);
	// 		}
	// 		for (auto &[a, b] : t) {
	// 			if (merge(dsu, sz, a, b)) r.push_back(adjacencyMatrix[a][b]);
	// 		}
	// 		assert(r.size() == n - 1);
	// 		scores.push_back(count_common_roads(r));
	// 	}

	// 	int least = scores[0], most = scores[0];
	// 	for (int &j : scores) least = min(least, j), most = max(most, j);

	// 	if (scores[0] != most) {
	// 		tWeight[i] = 1;
	// 		res.push_back(adjacencyMatrix[t[i].first][t[i].second]);
	// 		++sub[t[i].first];
	// 		++sub[t[i].second];
	// 		goldTree[t[i].first][t[i].second] = true;
	// 		goldTree[t[i].second][t[i].first] = true;
	// 	} 
	// }
	*/

	// Done:
	vector<int> nodeWeights(n, -1);
	for (int node = 0; node < n; ++node) {
		setDsu(dsu, sz);
		vector<int> r;
		for (auto &[adjacent, index] : adjacency[node]) {
			assert(merge(dsu, sz, node, adjacent));
			r.push_back(index);
		}

		int base = 0;
		for (int i = 0; i < n - 1; ++i) {
			if (merge(dsu, sz, t[i].first, t[i].second)) {
				r.push_back(adjacencyMatrix[t[i].first][t[i].second]);
				base += tWeight[i];
			}
		}
		assert(r.size() == n - 1);
		nodeWeights[node] = count_common_roads(r) - base;
	}

	// int cnt = 0;
	while (res.size() != n - 1) {
		// if (++cnt > 100) break;
		// cout << cnt << ' ' << res.size() << endl;
		// for (int &i : res) cout << i << ' ';
		// cout << endl;
		for (int node = 0; node < n; ++node) {
			if (nodeWeights[node] - sub[node] != 1) continue;
			int low = 0, high = adjacency[node].size() - sub[node];
			while (low < high - 1) {
				int mid = (low + high) / 2;
				setDsu(dsu, sz);
				vector<int> r;
				int shift = 0;
				for (int i = 0; i < mid; ++i) {
					if (goldTree[node][adjacency[node][i + shift].first]) {
						--i; ++shift;
						continue;
					}
					assert(merge(dsu, sz, node, adjacency[node][i + shift].first));
					r.push_back(adjacency[node][i + shift].second);
				}

				int base = 0;
				for (int i = 0; i < n - 1; ++i) {
					if (merge(dsu, sz, t[i].first, t[i].second)) {
						r.push_back(adjacencyMatrix[t[i].first][t[i].second]);
						base += tWeight[i];
					}
				}
				
				assert(r.size() == n - 1);
				if (count_common_roads(r) - base) high = mid;
				else low = mid;
			}

			int shift = 0;
			for (int i = 0; i <= low; ++i) {
				if (goldTree[node][adjacency[node][i + shift].first]) {
					--i; ++shift;
					continue;
				}
			}
			shift += low;
			res.push_back(adjacency[node][shift].second);
			++sub[node];
			++sub[adjacency[node][shift].first];
			goldTree[node][adjacency[node][shift].first] = true;
			goldTree[adjacency[node][shift].first][node] = true;
		}
	}

	return res;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 19 / 19
• Subtask 5: 0 / 30