Submission #58192

#	Time	Username	Problem	Language	Result	Execution time	Memory
58192		Crown	Simurgh (IOI17_simurgh)	C++14	30 / 100	173 ms	6608 KiB

simurgh

#include "simurgh.h"

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

// int count_common_roads(vector<int> vec)

const int maxn = 505;
const int maxm = maxn*maxn/2;

int n, m;
int edgeID[maxn][maxn];
vector<int> U, V;

vector<int> adj[maxn];

int par[maxn];
bool vis[maxn];
int dep[maxn];
int tree_score[maxm];

bool isInTree[maxm];
bool isNotBridge[maxm];
bool res[maxm];

vector<int> backedges; 

vector<int> output;

void find_tree(int u = 0, int p = -1)
{
	if(p != -1) par[u] = p;	
	vis[u] = true;
	for(auto v : adj[u])
	{
		if(!vis[v])
		{
			dep[v] = dep[u]+1;
			find_tree(v, u);
			isInTree[edgeID[u][v]] = true;
			output.push_back(edgeID[u][v]);
		}
		else if(v != p)
		{
			backedges.pb(edgeID[u][v]);
		}
	}
}

bool cmp(int a, int b)
{
	int ua = U[a], ub = U[b];
	int va = V[a], vb = V[b];
	return min(dep[ua], dep[va])< min(dep[ub], dep[vb]);
}

void delete_from_output(int u)
{
	vector<int> nou;
	for(auto x : output)
	{
		if(x == u) continue;
		nou.pb(x);
	}
	output = nou; 
}

void add_to_output(int u)
{
	output.pb(u);
}

int ask()
{
	return count_common_roads(output);
}
vector<int> find_roads(int _n, vector<int> _u, vector<int> _v)
{
	n = _n; m = _u.size();
	U = _u; V = _v;
	for(int i = 0; i< m; i++)
	{
		int u = U[i], v = V[i];
		edgeID[u][v] = edgeID[v][u] = i;
		adj[u].pb(v); adj[v].pb(u);
	}
	dep[0] = 1; find_tree();
	sort(backedges.begin(), backedges.end());
	backedges.resize(unique(backedges.begin(), backedges.end())-backedges.begin());
	sort(backedges.begin(), backedges.end(), cmp);
	int base_score = ask();
	for(auto edge : backedges)
	{
		int u = U[edge], v = V[edge];
		if(dep[u]< dep[v]) swap(u, v);
		int cur = u;
		add_to_output(edge);
		int mn = base_score, mx = base_score;
		while(cur != v)
		{
			int tp = par[cur];
			int id = edgeID[cur][tp];
			isNotBridge[id] = true;
			delete_from_output(id);
			tree_score[id] = ask();
			mn = min(tree_score[id], mn);
			mx = max(tree_score[id], mx);
			add_to_output(id);
			cur = tp;
		}
		delete_from_output(edge);
		cur = u;
		while(cur != v)
		{
			int tp = par[cur];
			int id = edgeID[cur][tp];
			if(mn == mx) res[id] = false;
			else if(tree_score[id] == mn) res[id] = true;
			else res[id] = false;
			cur = tp;
		}
		if(mn != mx && base_score == mn) res[edge] = true;
	}
	output.clear();
	for(int i = 0; i< m; i++)
	{
		if((!isNotBridge[i] and isInTree[i]) or res[i]) output.pb(i);
	}
	assert(ask() == n-1);
	return output;
}

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