Submission #1206632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206632		ericl23302	Simurgh (IOI17_simurgh)	C++20	0 / 100	0 ms	328 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] += b;
	return true;
}

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<pair<int, int>>> adjacencyMatrix(n, vector<pair<int, int>>(n, {0, -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]] = {1, i};
		adjacencyMatrix[v[i]][u[i]] = {1, i};
	}

	vector<pair<int, int>> t(n - 1);
	for (int i = 0; i < n - 1; ++i) t[i] = {i, i + 1};

	vector<int> res;
	vector<int> tWeight(n - 1, 0), dsu(n), sz(n);
	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].second);
			}
			for (auto &[a, b] : t) {
				if (merge(dsu, sz, a, b)) r.push_back(adjacencyMatrix[a][b].second);
			}
			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].second);
			++sub[t[i].first];
			++sub[t[i].second];
		} 
	}

	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].second);
				base += tWeight[i];
			}
		}
		assert(r.size() == n - 1);
		nodeWeights[node] = count_common_roads(r) - base;
	}

	while (res.size() != n - 1) {
		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 (nodeWeights[adjacency[node][i + shift].first] == sub[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].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 (nodeWeights[adjacency[node][i + shift].first] == sub[adjacency[node][i + shift].first]) {
					--i; ++shift;
					continue;
				}
			}
			shift += low;
			res.push_back(adjacency[node][shift].second);
			++sub[node];
			++sub[adjacency[node][shift].first];
		}
	}

	return res;
}

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