Submission #838247

#	Time	Username	Problem	Language	Result	Execution time	Memory
838247		Johann	Simurgh (IOI17_simurgh)	C++14	51 / 100	65 ms	4308 KiB

simurgh

#include "simurgh.h"
#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N;
vi U, V;
vvpii adj;
vi goldenTree;
const int NOTHING = 0;
const int FRONTIER = 1;
const int EXPLORED = 2;
vi status;
vvi edgesToCandidates;
vi tmpTree;
vi belongs;
int cntQueries;

vi askEdges;

void buildTree(int v)
{
	for (pii e : adj[v])
		if (status[e.first] == NOTHING && belongs[e.first] == -1)
		{
			belongs[e.first] = belongs[v];
			tmpTree.push_back(e.second);
			buildTree(e.first);
		}
		else if (status[e.first] == FRONTIER)
			edgesToCandidates[belongs[v]].push_back(e.second);
}

void findGoldenTree()
{
	if (sz(goldenTree) == N - 1)
		return;
	int groups = 0;
	edgesToCandidates.clear();
	tmpTree = vi(all(goldenTree));
	belongs.assign(N, -1);
	for (int v = 0; v < N; ++v)
		if (status[v] == NOTHING && belongs[v] == -1)
		{
			belongs[v] = groups++;
			edgesToCandidates.push_back(vi());
			buildTree(v);
			assert(!edgesToCandidates.empty());
		}

	vi toAdd;
	for (int g = 0; g < groups; ++g)
	{
		for (int g2 = 0; g2 < groups; ++g2)
			if (g2 != g)
				tmpTree.push_back(edgesToCandidates[g2].front());

		vi record(sz(edgesToCandidates[g]));
		for (int i = 0; i < sz(edgesToCandidates[g]); ++i)
		{
			tmpTree.push_back(edgesToCandidates[g][i]);
			++cntQueries;
			assert(!askEdges[edgesToCandidates[g][i]]);
			askEdges[edgesToCandidates[g][i]] = true;
			// assert(cntQueries <= 30000);
			record[i] = count_common_roads(tmpTree);
			tmpTree.pop_back();
		}

		int maxi = *max_element(all(record));
		for (int i = 0; i < sz(edgesToCandidates[g]); ++i)
			if (maxi == record[i])
				toAdd.push_back(edgesToCandidates[g][i]);

		for (int g2 = 0; g2 < groups; ++g2)
			if (g2 != g)
				tmpTree.pop_back();
	}

	for (int i = 0; i < N; ++i)
		if (status[i] == FRONTIER)
			status[i] = EXPLORED;
	// assert(!toAdd.empty());
	for (int x : toAdd)
	{
		if (status[U[x]] != NOTHING)
			status[V[x]] = FRONTIER;
		else
			status[U[x]] = FRONTIER;
		goldenTree.push_back(x);
	}
	findGoldenTree();
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v)
{
	N = n;
	U = u, V = v;
	adj = vvpii(n);
	for (int i = 0; i < sz(u); ++i)
		adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});

	cntQueries = 0;
	askEdges.assign(sz(u), 0);

	goldenTree.clear();
	status.assign(n, NOTHING);
	status[0] = FRONTIER;
	findGoldenTree();

	// cout << cntQueries << endl;

	return goldenTree;
}

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