Submission #475494

#	Time	Username	Problem	Language	Result	Execution time	Memory
475494		blue	Simurgh (IOI17_simurgh)	C++17	100 / 100	692 ms	17212 KiB

simurgh

#include "simurgh.h"
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

const int maxN = 500;
const int maxM = 500*499/2;

int N, M;

vector< vector<int> > edge_index(maxN, vector<int>(maxN, -1)); //index of edge in graph
vector<int> edge[maxN]; //list of edge destinations of each node in maain graph

vector<bool> edge_in_tree(maxM, 0); //is this edge index in the tree?

set<int> treeset; //set of edge indices in the basic spanning tree




vector<int> parent(maxN, -1); //parent of node in basic spanning tree
vector<int> depth(maxN, 0); //depth of node in basic spanning tree



const int unclear = -1;
const int good = 1;
const int bad = 0;

vector<bool> extra_visited(maxM, 0);

vector<int> state(maxM, unclear); //state of each edge.


void dfs(int u)
{
	// cerr << "u = " << u << '\n';
	for(int v: edge[u])
	{
		// cerr << u << " -> " << v << '\n';
		if(parent[u] == v || parent[v] != -1) continue;

		parent[v] = u;
		depth[v] = depth[u] + 1;

		edge_in_tree[ edge_index[u][v] ] = 1;
		treeset.insert(edge_index[u][v]);

		dfs(v);
	}
}

vector<int> findtree_ans(maxM, -1);

vector<int> get_vector(set<int> S)
{
	vector<int> K;
	for(int s:S) K.push_back(s);
	return K;
}





struct disjoint_set
{
	int N;
	vector<int> parent;
	vector<int> subtree;

	disjoint_set()
	{
		;
	}

	disjoint_set(int N_)
	{
		N = N_;
		parent = vector<int>(N);
		subtree = vector<int>(N, 1);
		for(int i = 0; i < N; i++) parent[i] = i;
	}

	int root(int u)
	{
		while(parent[u] != u) u = parent[u];
		return u;
	}

	bool connected(int u, int v)
	{
		return root(u) == root(v);
	}

	void join(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(connected(u, v)) return;
		if(subtree[u] < subtree[v]) swap(u, v);
		parent[v] = u;
		subtree[u] += subtree[v];
	}
};







vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
	// cerr << "check zero\n";
//PART ONE
	N = n;
	M = (int)u.size();

	for(int j = 0; j < M; j++)
	{
		edge_index[ u[j] ][ v[j] ] = edge_index[ v[j] ][ u[j] ] = j;
		edge[ u[j] ].push_back( v[j] );
		edge[ v[j] ].push_back( u[j] );
	}
		// cerr << "check2\n";

	parent[0] = 0;
	dfs(0);
	// cerr << "check3\n";

	vector<int> Q;
	for(int j = 0; j < M; j++)
		if(edge_in_tree[j])
			Q.push_back(j);

	int basic_query = count_common_roads(Q);
	Q.clear();

	// cerr << "check 1\n";

	// cerr << "check4\n";



	for(int j = 0; j < M; j++)
	{
		if(edge_in_tree[j]) continue;
			// cerr << "check5 " << j << '\n';

		vector<int> tree_path;
		int U = u[j], V = v[j];
		if(depth[U] > depth[V]) swap(U, V);
		// cerr << depth[V] - depth[U] << '\n';
		while(depth[V] != depth[U])
		{
			// cerr << "k = " << k << '\n';
			tree_path.push_back( edge_index[ V ][ parent[V] ] );
			V = parent[V];
		}
		// cerr << "check6 " << j << '\n';
		// cerr << U << ' ' << V << ' ' << depth[U] << ' ' << depth[V] << '\n';
		while(U != V)
		{
			tree_path.push_back( edge_index[U][ parent[U] ] );
			tree_path.push_back(edge_index[V][parent[V]]);
			U = parent[U];
			V = parent[V];
		}

		for(int t: tree_path)
			extra_visited[t] = 1;

		// cerr << "check7 " << j << '\n';

		vector<int> known;
		vector<int> unknown;
		int known_count = 0;
		for(int t: tree_path)
		{
			if(state[t] != unclear)
			{
				known.push_back(t);
				known_count++;
			}
			else
			{
				unknown.push_back(t);
			}
		}

		// cerr << "check8 " << j << '\n';

		if(known_count == (int)tree_path.size())
			continue;
		else if(known_count != 0)
		{
			treeset.insert(j);


			treeset.erase(known[0]);

			int this_basic = count_common_roads(get_vector(treeset));
			int cycle_weight = this_basic + state[known[0]];

			treeset.insert(known[0]);

			for(int u: unknown)
			{
				treeset.erase(u);
				state[u] = cycle_weight - count_common_roads(get_vector(treeset));
				treeset.insert(u);
			}

			treeset.erase(j);
		}
		else if(known_count == 0)
		{
			vector< pair<int, int> > cycle_elements;
			cycle_elements.push_back(make_pair(basic_query, j));
			for(int t: tree_path)
			{
				treeset.erase(t);
				treeset.insert(j);

				findtree_ans[t] = count_common_roads(get_vector(treeset));
				cycle_elements.push_back(make_pair(findtree_ans[t], t));

				treeset.erase(j);
				treeset.insert(t);
			}
			sort(cycle_elements.begin(), cycle_elements.end());

			bool good_flag = 0;

			for(int x = (int)cycle_elements.size() - 1; x >= 0; x--)
			{
				if(x < (int)cycle_elements.size() - 1 && cycle_elements[x].first != cycle_elements[x+1].first)
					good_flag = 1;

				if(good_flag)
					state[ cycle_elements[x].second ] = good;
				else
					state[ cycle_elements[x].second ] = bad;
			}
		}
		// cerr << "check9 " << j << '\n';
	}

	for(int e: treeset)
		if(extra_visited[e] == 0)
			state[e] = good;

	// cerr << "tree and states: \n";
	//
	// for(int j = 0; j < M; j++)
	// {
	// 	if(edge_in_tree[j])
	// 	{
	// 		cerr << u[j] << ' ' << v[j] << ' ' << state[j] << '\n';
	// 	}
	// }
	// cerr << "check 2\n";












//PART TWO


	set<int> potential_new_neighbors[N];
	vector<int> new_neighbors_count(N, 0);
	for(int U = 0; U < N; U++)
	{
		for(int V = 0; V < N; V++)
		{
			if(U == V) continue;
			if(state[ edge_index[U][V] ] == unclear)
			{
				potential_new_neighbors[U].insert(V);
			}
		}
	}
	// cerr << "check 3\n";
	//
	// for(int t: treeset) cerr << t << ' ';
	// cerr << '\n';

	for(int U = 0; U < N; U++)
	{
		// cerr << "U = " << U << '\n';
		vector<int> query_vector;
		disjoint_set DSU(N);
		for(int V = 0; V < N; V++)
		{
			if(U == V) continue;

			if(edge_index[U][V] != -1)
			{
				if(state[ edge_index[U][V] ] == good)
					new_neighbors_count[U]--;

				DSU.join(U, V);
				query_vector.push_back(edge_index[U][V]);
			}
		}

		// cerr << "qv = ";
		// for(int qv: query_vector) cerr << qv << ' ';
		// cerr << '\n';
		//
		// for(int i = 0; i < N; i++)
		// 	cerr << DSU.root(i) << ' ';
		// cerr << '\n';

		for(int t: treeset)
		{
			// cerr << u[t] << ' ' << v[t] << ' ' << DSU.connected(u[t], v[t]) << '\n';
			if(!DSU.connected(u[t], v[t]))
			{
				// cerr << "joined!\n";
				DSU.join(u[t], v[t]);
				// cerr << u[t] << ' ' << v[t] << ' ' << DSU.connected(u[t], v[t]) << '\n';
				query_vector.push_back(t);
				if(state[t] == good)
					new_neighbors_count[U]--;

				// for(int i = 0; i < N; i++)
				// 	cerr << DSU.root(i) << ' ';
				// cerr << '\n';
			}
			// cerr << "\n";
		}
		// for(int i = 0; i < N; i++)
		// 	cerr << DSU.root(i) << ' ';
		// cerr << '\n';

		new_neighbors_count[U] += count_common_roads(query_vector);
	}
	// cerr << "check 4\n";





	for(int Z = 1; Z <= N; Z++)
	{
		int U = -1;
		for(int y = 0; y < N; y++)
		{
			if(new_neighbors_count[y] == 1)
			{
				U = y;
				break;
			}
		}
		if(U == -1) break;

		vector<int> candidates;
		for(int V = 0; V < N; V++)
		{
			if(U == V) continue;
			if(edge_index[U][V] == -1) continue;

			if(state[ edge_index[U][V] ] == unclear)
				candidates.push_back(V);
		}

		int lo = 0;
		int hi = (int)candidates.size() - 1;
		while(lo != hi)
		{
			int mid = (lo+hi)/2;

			int prefix_candidates = 0;

			disjoint_set DSU(N);
			vector<int> query_vector;
			for(int i = 0; i <= mid; i++)
			{
				DSU.join(U, candidates[i]);
				query_vector.push_back(  edge_index[U][candidates[i]] );
			}

			for(int t: treeset)
			{
				if(DSU.connected(u[t], v[t])) continue;
				prefix_candidates -= state[ edge_index[u[t]][v[t]] ];
				DSU.join(u[t], v[t]);
				query_vector.push_back(t);
			}

			prefix_candidates += count_common_roads(query_vector);

			if(prefix_candidates >= 1) hi = mid;
			else lo = mid+1;
		}

		for(int c: candidates)
		{
			if(c == candidates[lo])
			{
				state[ edge_index[U][c] ] = good;
				new_neighbors_count[c]--;
			}
			else
			{
				state[ edge_index[U][c] ] = bad;
			}

			potential_new_neighbors[c].erase(U);
			potential_new_neighbors[U].erase(c);

			new_neighbors_count[U]--;
		}
	}
	// cerr << "check 5\n";



	// for(int j = 0; j < M; j++) cerr << state[j] << ' ';
	// cerr << '\n';



	vector<int> res;
	for(int j = 0; j < M; j++)
		if(state[j] == good)
		{
			// cerr << "adding " << j << '\n';
			res.push_back(j);
		}

	return res;
}

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