Submission #65192

#	Time	Username	Problem	Language	Result	Execution time	Memory
65192		MatheusLealV	Simurgh (IOI17_simurgh)	C++17	13 / 100	166 ms	15672 KiB

simurgh

#include "simurgh.h"
#define N 225000
#define f first
#define ss second
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n, m, peso[N],ok[N], st[N], nivel[N], ans[N], valor;

pii E[N], pai[N];

vector<pii> grafo[N], tree[N];

vector<int> save;

void dfs(int x)
{
	ok[x] = 1;

	random_shuffle(grafo[x].begin(), grafo[x].end());

	for(auto v: grafo[x])
	{
		if(ok[v.f]) continue;

		tree[x].push_back({v.f, v.ss});

		tree[v.f].push_back({x, v.ss});

		pai[v.f] = {x, v.ss};

		nivel[v.f] = nivel[x] + 1;

		save.push_back(v.ss);

		st[v.ss] = 1;

		dfs(v.f);
	}
}

int checa1(int antiga, int nova)
{
	vector<int> aux;

	for(auto x: save)
	{
		if(x == antiga) continue;

		aux.push_back(x);
	}

	aux.push_back(nova);

	int val = count_common_roads(aux);

	if(val > valor) return 1;

	if(val < valor) return -1;

	return ans[antiga];
}

int checa2(int antiga, int nova)
{
	vector<int> aux;

	for(auto x: save)
	{
		if(x == antiga) continue;

		aux.push_back(x);
	}

	aux.push_back(nova);

	int val = count_common_roads(aux);

	if(val > valor) return 1;

	if(val < valor) return -1;

	return 0;
}

void solve(int x)
{
	int u = E[x].f, v = E[x].ss, pronto = -1;

	vector<int> path;

	while(u != v)
	{
		if(nivel[u] > nivel[v])
		{
			int up = pai[u].f, ed = pai[u].ss;

			path.push_back(ed);

			if(ans[ed] != 0)
			{
				pronto = ed;

				break;
			}

			u = up;
		}

		else
		{
			int up = pai[v].f, ed = pai[v].ss;

			path.push_back(ed);

			if(ans[ed] != 0)
			{
				pronto = ed;
			}

			v = up;			
		}
	}

	//cout<<"CHECA XIZ "<<x<<"\n";

	if(pronto != -1 or ans[x] != 0)
	{
		if(ans[x] == 0) ans[x] = checa1(pronto,x);

		for(auto y: path)
		{
			if(ans[y] != 0) continue;

			//cout<<"CHECA 1 "<<y<<"\n";

			int val = checa1(y, x);

			if(val > 0) ans[y] = -1;

			else if(val < 0) ans[y] = 1;

			else ans[y] = ans[x];
		}
	}

	else
	{
		for(auto y: path)
		{
			//cout<<"REMOVE "<<y<<" ADD "<<x<<"\n";

			//cout<<"CHECA 2 "<<y<<"\n";

			int val = checa2(y, x);

			if(val == 1)
			{
				ans[x] = 1;

				ans[y] = -1;
			}

			if(val == -1)
			{
				ans[x] = -1;

				ans[y] = 1;
			}
		}

		if(ans[x] == 0)
		{
			ans[x] = -1;

			for(auto y: path) ans[y] = -1;
		}
	}
}

vector<int> find_roads(int ni, vector<int> u, vector<int> v)
{
	n = ni, m = (int)u.size();

	for(int i = 0; i < m; i++)
	{
		E[i] = {u[i], v[i]};

		grafo[u[i]].push_back({v[i], i});

		grafo[v[i]].push_back({u[i], i});
	}

	pai[0] = {0, 0};

	dfs(0);

	valor = count_common_roads(save);

	if(valor == n - 1) return save;

	for(int i = 0; i < m; i++)
	{
		if(st[i]) continue;

		//cout<<"OK "<<i<<"\n";

		solve(i);

	}

	vector<int> resp;

	for(int i = 0; i < m; i++)
	{
		if(ans[i] >= 1) resp.push_back(i);
	}

	sort(resp.begin(), resp.end());

	return resp;
}

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