oj.uz

Submission #259210

# Submission time Handle Problem Language Result Execution time Memory
259210 2020-08-07T12:02:18 Z GREGOIRELC Simurgh (IOI17_simurgh) C++14
0 / 100
 195 ms 3968 KB 
#include "simurgh.h"
#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<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);
			}
		}
	}
}

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);
				}
			}
		}
		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);
				}
			}
		}
	}
	return result;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Incorrect 0 ms 256 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Incorrect 0 ms 256 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Incorrect 0 ms 256 KB WA in grader: NO
10 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Correct 0 ms 256 KB correct
3 Incorrect 195 ms 3968 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 256 KB correct
3 Correct 0 ms 256 KB correct
4 Correct 0 ms 256 KB correct
5 Correct 0 ms 256 KB correct
6 Correct 0 ms 256 KB correct
7 Correct 1 ms 256 KB correct
8 Correct 0 ms 256 KB correct
9 Incorrect 0 ms 256 KB WA in grader: NO
10 Halted 0 ms 0 KB -