Submission #137723

#	Time	Username	Problem	Language	Result	Execution time	Memory
137723		Mahdi_Jfri	Simurgh (IOI17_simurgh)	C++14	100 / 100	386 ms	8176 KiB

simurgh

#include "simurgh.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e2 + 20;
const int maxm = maxn * maxn + 20;

int from[maxm] , to[maxm] , par[maxn] , h[maxn] , is[maxm] , ed[maxm] , num;

vector<int> adj[maxn] , bc[maxn] , ind;

bool visited[maxn] , tree[maxm];

void plant(int v)
{
	visited[v] = 1;
	for(auto e : adj[v])
	{
		int u = from[e] ^ to[e] ^ v;
		if(!visited[u])
		{
			ind.pb(e);
			h[u] = h[v] + 1;
			par[u] = e;
			tree[e] = 1;
			plant(u);
		}
		else if(h[u] < h[v] - 1)
			bc[v].pb(e);
	}
}

vector<int> rem(vector<int> x , int y)
{
	vector<int> nw;
	for(auto k : x)
		if(k != y)
			nw.pb(k);

	return nw;
}

bool cmp(int x , int y)
{
	x = min(h[from[x]] , h[to[x]]);
	y = min(h[from[y]] , h[to[y]]);

	return x > y;
}

int wtf[maxm];

int get(vector<int> &bc , int sz)
{
	if(!sz)
		return 0;

	vector<int> shit;
	for(int i = 0; i < sz; i++)
	{
		int e = bc[i];
		tree[wtf[e]] = 0;
		shit.pb(e);
	}

	int ts = 0;
	for(auto x : ind)
		if(tree[x])
		{
			if(is[x] == 1)
				ts++;
			shit.pb(x);
		}

	for(int i = 0; i < sz; i++)
	{
		int e = bc[i];
		tree[wtf[e]] = 1;
	}

	return count_common_roads(shit) - ts;
}

void dfs(int v)
{
	for(auto e : adj[v])
	{
		int u = from[e] ^ to[e] ^ v;
		if(h[u] == h[v] + 1)
			dfs(u);
	}

	if(bc[v].empty())
		return;

	int last = v;

	sort(bc[v].begin() , bc[v].end() , cmp);
	for(auto e : bc[v])
	{
		while(!last);
		wtf[e] = par[last];
		last = from[e] ^ to[e] ^ v;
	}

	int k = bc[v].size() , st = 0 , stl = 0 , shit = get(bc[v] , k);
	while(k && shit > st)
	{
		int l = stl , r = k;
		while(r - l > 1)
		{
			int m = (l + r) / 2;
			if(get(bc[v] , m) > st)
				r = m;
			else
				l = m;
		}

		is[bc[v][r - 1]] = 1;
		stl = r;
		st++;
	}

}

vector<int> find_roads(int n,vector<int> A,vector<int> B)
{
	n = n;
	int m = A.size();
	for(int i = 0; i < m; i++)
	{
		int a = A[i] , b = B[i];

		adj[a].pb(i);
		adj[b].pb(i);

		from[i] = a , to[i] = b;
	}

	plant(0);

	memset(ed , -1 , sizeof ed);

	num = count_common_roads(ind);
	for(int i = 0; i < m; i++)
		if(!tree[i])
		{
			int v = from[i] , u = to[i];
			if(h[v] < h[u])
				swap(v , u);

			vector<int> ed;

			bool has0 = 0;
			while(v != u)
			{
				if(is[par[v]] == 0)
					has0 = 1;

				ed.pb(par[v]);
				v = from[par[v]] ^ to[par[v]] ^ v;
			}

			if(!has0)
				continue;

			vector<int> eq;
			for(auto e : ed)
			{
				if(is[e] != 0 && is[i] != 0)
					continue;

				ind = rem(ind , e);
				ind.pb(i);
				int nw = count_common_roads(ind);
				ind.pop_back() , ind.pb(e);

				if(nw == num)
				{
					if(is[e] != 0)
						is[i] = is[e];
					else
						eq.pb(e);
				}
				else if(nw == num + 1)
				{
					is[i] = 1;
					is[e] = -1;
				}
				else
				{
					is[e] = 1;
					is[i] = -1;
				}
			}

			if((int)eq.size() == (int)ed.size())
				is[i] = -1;

			for(auto e : eq)
				is[e] = is[i];
		}

	for(auto x : ind)
		if(is[x] == 0)
			is[x] = 1;

	dfs(0);

	vector<int> ans;
	for(int i = 0; i < m; i++)
	{
		if(!is[i])
			is[i] = -1;
		if(is[i] == 1)
			ans.pb(i);
	}

	while(count_common_roads(ans) != n - 1);

	return ans;
}

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