Submission #259217

#	Time	Username	Problem	Language	Result	Execution time	Memory
259217		GREGOIRELC	Simurgh (IOI17_simurgh)	C++14	0 / 100	189 ms	3412 KiB

simurgh

#include "simurgh.h"
#include <iostream>
#include <queue>

using namespace std;

const int MAX_NOEUD = 500;

int nbNoeud, nbArc;
int groupe[MAX_NOEUD];
bool estImpossible[MAX_NOEUD];
vector<int> result;
vector<int> curArbre;
vector<int> reserve[MAX_NOEUD];
vector<pair<int, int> > graphe[MAX_NOEUD];

int retourne_Groupe(int a)
{
	if(groupe[a] == a)
	{
		return a;
	}
	groupe[a] = retourne_Groupe(groupe[a]);
	return groupe[a];
}

void fusionne(int a, int b)
{
	int gpA = retourne_Groupe(a), gpB = retourne_Groupe(b);
	groupe[gpA] = gpB;
}

void construire_Arbre(int iNoeud)
{
	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		groupe[iNoeud] = iNoeud;
	}
	curArbre.clear();

	queue<int> noeudsEnCours;
	noeudsEnCours.push((iNoeud + 1) % nbNoeud);

	while(!noeudsEnCours.empty())
	{
		int curNoeud = noeudsEnCours.front();
		noeudsEnCours.pop();
		for(pair<int, int> voisin : graphe[curNoeud])
		{
			if(voisin.first == iNoeud)
			{
				continue;
			}
			if(retourne_Groupe(voisin.first) != retourne_Groupe(curNoeud))
			{
				fusionne(voisin.first, curNoeud);
				noeudsEnCours.push(voisin.first);
				curArbre.push_back(voisin.second);
			}
		}
	}
}

void affiche_Arbre()
{
	for(int i : curArbre)
	{
		cout << i << endl;
	}
	cout << endl;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v)
{
	nbNoeud = n;
	nbArc = (int)u.size();
	for(int iArc = 0; iArc < nbArc; iArc++)
	{
		graphe[u[iArc]].push_back({v[iArc], iArc});
		graphe[v[iArc]].push_back({u[iArc], iArc});
	}

	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		construire_Arbre(iNoeud);

		if((int)curArbre.size() < nbNoeud - 2)
		{
			estImpossible[iNoeud] = true;
			for(pair<int, int> voisin : graphe[iNoeud])
			{
				if(voisin.first < iNoeud && estImpossible[voisin.first])
				{
					result.push_back(voisin.second);
				}
			}
			for(int val : reserve[iNoeud])
			{
				result.push_back(val);
			}
		}
		else
		{
			int maxi = 0;
			vector<int> interessante;
			for(pair<int, int> voisin : graphe[iNoeud])
			{
				curArbre.push_back(voisin.second);
				int val = count_common_roads(curArbre);
				if(val > maxi)
				{
					interessante.clear();
					maxi = val;
				}
				if(val == maxi)
				{
					interessante.push_back(voisin.second);
				}
				curArbre.pop_back();
			}
			for(int arc : interessante)
			{
				if((u[arc] == iNoeud && v[arc] < iNoeud) || (v[arc] == iNoeud && u[arc] < iNoeud))
				{
					result.push_back(arc);
				}
				else
				{
					int dest = u[arc];
					if(dest == iNoeud)
					{
						dest = v[arc];
					}
					reserve[dest].push_back(iNoeud);
				}
			}
		}
	}
	return result;
}

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