Submission #1054011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054011		Gromp15	Simurgh (IOI17_simurgh)	C++17	100 / 100	179 ms	6224 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"
#define ar array
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct dsu {
	vector<int> p, size;
	dsu(int n) : p(n), size(n, 1) {
		iota(all(p), 0);
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	bool merge(int a, int b) {
		a = get(a), b = get(b);
		if (a == b) return 0;
		if (size[a] < size[b]) swap(a, b);
		size[a] += size[b], p[b] = a;
		return 1;
	}
};

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	int m = sz(u);
	vector<vector<ar<int, 2>>> adj(n);
	for (int i = 0; i < m; i++) {
		adj[u[i]].push_back({v[i], i});
		adj[v[i]].push_back({u[i], i});
	}
	vector<int> type(m, -1);
	vector<ar<int, 2>> p(n, {-1, -1});
	vector<int> tin(n), low(n);
	int timer = 0;
	vector<int> edges;
	auto dfs = [&](auto&& s, int v) -> void {
		tin[v] = low[v] = ++timer;
		for (auto [u, idx] : adj[v]) if (u != p[v][0]) {
			if (!tin[u]) {
				p[u] = {v, idx}, edges.emplace_back(idx), s(s, u);
				ckmin(low[v], low[u]);
				if (low[u] > tin[v]) type[idx] = 1;
			}
			else {
				ckmin(low[v], tin[u]);
			}
		}
	};
	dfs(dfs, 0);
	int orig = count_common_roads(edges);
	for (int v = 0; v < n; v++) {
		for (auto [u, idx] : adj[v]) if (u != p[v][0] && tin[u] < tin[v]) {
			//cout << "ASK " << v << " " << u << '\n';
			vector<int> cur_edges;
			for (int tmp = v; tmp != u; tmp = p[tmp][0]) {
				int eidx = p[tmp][1];
				cur_edges.emplace_back(eidx);
			}
			int not_gold = -1, gold = -1;
			bool skip = 1;
			for (int e : cur_edges) { 
				if (!~type[e]) skip = 0;
				if (!type[e]) not_gold = e;
				if (type[e] == 1) gold = e;
			}
			if (skip) continue;
			if (~not_gold) {
				//cout << "Hi not gold " << not_gold << '\n';
				int orig2 = -1;
				{
					auto edges2 = edges;
					edges2.erase(find(all(edges2), not_gold));
					edges2.emplace_back(idx);
					orig2 = count_common_roads(edges2);
				}
				for (int e : cur_edges) if (!~type[e]) {
					auto edges2 = edges;
					edges2.erase(find(all(edges2), e));
					edges2.emplace_back(idx);
					type[e] = count_common_roads(edges2) < orig2;
				}
			}
			else if (~gold) {
				//cout << "Hi " << gold << '\n';
				int orig2 = -1;
				{
					auto edges2 = edges;
					edges2.erase(find(all(edges2), gold));
					edges2.emplace_back(idx);
					orig2 = count_common_roads(edges2);
				}
				for (int e : cur_edges) if (!~type[e]) {
					auto edges2 = edges;
					edges2.erase(find(all(edges2), e));
					edges2.emplace_back(idx);
					type[e] = count_common_roads(edges2) == orig2;
				}
			}
			else {
				int mn = orig, mx = orig;
				vector<int> val(sz(cur_edges));
				assert(sz(val) > 1);
				for (int i = 0; i < sz(cur_edges); i++) {
					int e = cur_edges[i];
					auto edges2 = edges;
					edges2.erase(find(all(edges2), e));
					edges2.emplace_back(idx);
					int res = count_common_roads(edges2);
					ckmin(mn, res), ckmax(mx, res);
					val[i] = res;
				}
				/*
				cout << "MN " << mn << " " << mx << '\n';
				cout << "Edges\n";
				for (int e : cur_edges) cout << e << " ";
				cout << '\n';
				*/
				if (mn == mx) {
					for (int e : cur_edges) type[e] = 0;
				}
				else {
					assert(mx - 1 == mn);
					for (int i = 0; i < sz(cur_edges); i++) {
						//cout << "CUR " << cur_edges[i] << " " << val[i] << '\n';
						type[cur_edges[i]] = val[i] < mx;
					}
				}
			}
		}
	}
	//for (int i = 0; i < m; i++) cout << u[i] << " " << v[i] << " " << type[i] << '\n';
	auto ask = [&](vector<int> ve) {
		dsu d(n);
		vector<int> new_edges;
		for (int e : ve) {
			assert(d.merge(u[e], v[e]));
			new_edges.emplace_back(e);
		}
		int cnt = 0;
		for (int e : edges) {
			if (d.merge(u[e], v[e])) {
				new_edges.emplace_back(e);
				cnt += type[e];
			}
		}
		return count_common_roads(new_edges) > cnt;
	};
	vector<int> ans;
	for (int i = 1; i < n; i++) {
		vector<int> side;
		for (auto [u, idx] : adj[i]) if (u < i) side.emplace_back(idx);
		auto side2 = side;
		while (1) {
			if (side.empty() || !ask(side)) break;
			while (side.size() > 1) {
				vector<int> hf(side.begin(), side.begin() + side.size() / 2);
				if (ask(hf)) swap(side, hf);
				else side = vector<int>(side.begin() + side.size() / 2, side.end());
			}
			assert(side.size() == 1);
			ans.emplace_back(side[0]);
			side2.erase(find(all(side2), side[0]));
			side = side2;
		}
	}
	return ans;
}

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