Submission #259374

#	Time	Username	Problem	Language	Result	Execution time	Memory
259374		GREGOIRELC	Simurgh (IOI17_simurgh)	C++14	0 / 100	197 ms	4088 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 dv[MAX_NOEUD];
bool estImpossible[MAX_NOEUD];
int valide[MAX_NOEUD];
vector<int> result;
vector<int> curArbre;
vector<int> arcParType[MAX_NOEUD];
vector<int> U, V;
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 noeudSuppr)
{
	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		groupe[iNoeud] = iNoeud;
		dv[iNoeud] = false;
	}
	curArbre.clear();

	queue<int> noeudsEnCours;
	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		if(iNoeud == noeudSuppr || dv[iNoeud])
		{
			continue;
		}
		noeudsEnCours.push(iNoeud);
		while(!noeudsEnCours.empty())
		{
			int curNoeud = noeudsEnCours.front();
			noeudsEnCours.pop();
			dv[curNoeud] = true;
			for(pair<int, int> voisin : graphe[curNoeud])
			{
				if(voisin.first == noeudSuppr)
				{
					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;
}

void test(int curNoeud)
{
	vector<int> typeDispo;
	for(pair<int, int> voisin : graphe[curNoeud])
	{
		if(arcParType[groupe[voisin.first]].size() == 0)
		{
			typeDispo.push_back(groupe[voisin.first]);
		}
		arcParType[groupe[voisin.first]].push_back(voisin.second);
	}
	for(size_t curType = 0; curType < typeDispo.size(); curType++)
	{
		for(size_t otherType = 0; otherType < typeDispo.size(); otherType++)
		{
			if(otherType != curType)
			{
				curArbre.push_back(arcParType[typeDispo[otherType]][0]);
			}
		}
		int maxi = 0;
		vector<int> arcBon;
		if(valide[curNoeud] != -1)
		{
			curArbre.push_back(valide[curNoeud]);
			maxi = count_common_roads(curArbre);
			curArbre.pop_back();
		}
		for(int voisin : arcParType[typeDispo[curType]])
		{
			int dest = U[voisin];
			if(dest == curNoeud)
			{
				dest = V[voisin];
			}
			/*if(valide[curNoeud] != -1 && dest > curNoeud)
			{
				continue;
			}*/
			curArbre.push_back(voisin);
			int val = count_common_roads(curArbre);
			if(val > maxi)
			{
				arcBon.clear();
				maxi = val;
			}
			if(val == maxi)
			{
				arcBon.push_back(voisin);
			}
			curArbre.pop_back();
		}
		for(int i : arcBon)
		{
			int dest = U[i];
			if(dest == curNoeud)
			{
				dest = V[i];
			}
			valide[dest] = i;
			if(dest > curNoeud)
			{
				continue;
			}
			result.push_back(i);
		}
		for(int i = 0; i < (int)typeDispo.size() - 1; i++)
		{
			curArbre.pop_back();
		}
	}
	for(int i : typeDispo)
	{
		arcParType[i].clear();
	}
}

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});
		U.push_back(u[iArc]);
		V.push_back(v[iArc]);
	}
	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		valide[iNoeud] = -1;
	}

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

		test(iNoeud);
	}
	return result;
}

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