Submission #1080292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080292		Joshua_Andersson	Simurgh (IOI17_simurgh)	C++14	19 / 100	1106 ms	16128 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

struct UF
{
	vi par;
	UF(int n) : par(n)
	{
		rep(i, n)par[i] = i;
	}
	int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
	void merge(int a, int b)
	{
		a = find(a); b = find(b);
		if (a == b) return;
		par[b] = a;
	}
};

vi a, b;
int n;
vector<p2> spanning;
int forest_query(vi edges)
{
	vi q;
	UF uf(n);
	repe(u, edges)
	{
		q.emplace_back(u);
		if (uf.find(a[u]) == uf.find(b[u])) assert(0);
		uf.merge(a[u], b[u]);
	}
	int num_good = 0;
	repe(s, spanning)
	{
		if (uf.find(a[s.first]) == uf.find(b[s.first])) continue;
		uf.merge(a[s.first], b[s.first]);
		num_good += s.second;
		q.push_back(s.first);
	}
	assert(sz(q) < n);
	return count_common_roads(q) - num_good;
}

std::vector<int> find_roads(int N, std::vector<int> A, std::vector<int> B) {
	a = A;
	b = B;
	n = N;
	if (n==2)
	{
		return { 0 };
	}
	int m = sz(a);

	UF uf(n);
	vvi adj(n);
	rep(i, m)
	{
		if (uf.find(a[i]) != uf.find(b[i]))
		{
			uf.merge(a[i], b[i]);
			spanning.emplace_back(i, -1);
			adj[a[i]].push_back(i);
			adj[b[i]].push_back(i);
		}
	}
	

	
	assert(sz(spanning) == n - 1);
	vi q(n - 1);
	rep(i, n-1)
	{
		int eind = spanning[i].first;
		vi trongle;
		int u = a[eind];
		int v = b[eind];

		trongle.push_back(eind);
		repe(e, adj[u])
		{
			if (e != eind)
			{
				trongle.push_back(e);
				break;
			}
		}
		if (sz(trongle)==1)
		{
			repe(e, adj[v])
			{
				if (e != eind)
				{
					trongle.push_back(e);
					break;
				}
			}
		}
		
		set<int> nodes;
		nodes.insert(a[trongle[0]]);
		nodes.insert(b[trongle[0]]);
		nodes.insert(a[trongle[1]]);
		nodes.insert(b[trongle[1]]);
		trongle = vi();
		
		rep(j, m)
		{
			if (nodes.find(a[j])!=nodes.end()&&nodes.find(b[j])!=nodes.end())
			{
				trongle.push_back(j);
			}
		}

		UF uf(n);
		uf.merge(a[trongle[0]], b[trongle[0]]);
		uf.merge(a[trongle[1]], b[trongle[1]]);
		uf.merge(a[trongle[2]], b[trongle[2]]);
		vi sp;
		rep(e, m)
		{
			if (uf.find(a[e]) == uf.find(b[e])) continue;
			uf.merge(a[e], b[e]);
			sp.push_back(e);
		}

		int m = 0;
		vector<p2> res;
		rep(j, 3)
		{

			vi q;
			rep(k, 3)
			{
				if (j == k) continue;
				q.push_back(trongle[k]);
			}
			repe(s, sp) q.push_back(s);
			
			int r = count_common_roads(q);
			m = max(m, r);
			res.emplace_back(trongle[j], r);
		}
		rep(j, 3)
		{
			if (res[j].first == eind)
			{
				spanning[i].second = res[j].second < m;
				break;
			}
		}
	}

	vector<set<int>> edges(n);
	rep(i, m)
	{
		edges[a[i]].insert(i);
		edges[b[i]].insert(i);
	}
	queue<int> leaf;
	vi deg(n);
	rep(i, n)
	{
		deg[i] = forest_query(vi(all(edges[i])));
		if (deg[i] == 1) leaf.push(i);
	}

	int baseline = forest_query(vi());
	vi par(n, -1);
	while (sz(leaf))
	{
		int u = leaf.front();
		leaf.pop();

		if (deg[u] == 0) break;
		assert(deg[u] == 1);
		int lo = -1;
		int hi = sz(edges[u]);
		while (lo+1<hi)
		{
			int mid = (lo + hi) / 2;
			vi q;
			auto start = edges[u].begin();
			rep(i, mid + 1)
			{
				q.push_back(*start);
				start++;
			}
			if (forest_query(q))
			{
				hi = mid;
			}
			else lo = mid;
		}
		auto start = edges[u].begin();
		rep(i, hi) start = next(start);
		int e = *start;
		int v = a[e] == u ? b[e] : a[e];
		edges[v].erase(e);
		deg[v]--;
		if (deg[v]==1)
		{
			leaf.push(v);
		}
		par[u] = e;
	}

	vi r;
	rep(i, n) if (par[i] != -1)r.push_back(par[i]);
	int common = count_common_roads(r);
	assert(common == n - 1);
	return r;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:187:6: warning: unused variable 'baseline' [-Wunused-variable]
  187 |  int baseline = forest_query(vi());
      |      ^~~~~~~~

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