oj.uz

Submission #259293

# Submission time Handle Problem Language Result Execution time Memory
259293 2020-08-07T13:58:27 Z GREGOIRELC Simurgh (IOI17_simurgh) C++14
30 / 100
 247 ms 4728 KB 
#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];
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;
		for(int voisin : arcParType[typeDispo[curType]])
		{
			int dest = U[voisin];
			if(dest == curNoeud)
			{
				dest = V[voisin];
			}
			curArbre.push_back(voisin);
			int val = count_common_roads(curArbre);
			//cout << curNoeud << " " << voisin << " " << val << endl;
			//affiche_Arbre();
			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];
			}
			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++)
	{
		construire_Arbre(iNoeud);

		test(iNoeud);
	}
	return result;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 4 ms 384 KB correct
15 Correct 4 ms 384 KB correct
16 Correct 4 ms 472 KB correct
17 Correct 4 ms 384 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 4 ms 384 KB correct
20 Correct 4 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 3 ms 436 KB correct
23 Correct 2 ms 384 KB correct
24 Correct 2 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 2 ms 384 KB correct
27 Correct 3 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 2 ms 384 KB correct
31 Correct 3 ms 384 KB correct
32 Correct 3 ms 384 KB correct
33 Correct 2 ms 384 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 4 ms 384 KB correct
15 Correct 4 ms 384 KB correct
16 Correct 4 ms 472 KB correct
17 Correct 4 ms 384 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 4 ms 384 KB correct
20 Correct 4 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 3 ms 436 KB correct
23 Correct 2 ms 384 KB correct
24 Correct 2 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 2 ms 384 KB correct
27 Correct 3 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 2 ms 384 KB correct
31 Correct 3 ms 384 KB correct
32 Correct 3 ms 384 KB correct
33 Correct 2 ms 384 KB correct
34 Incorrect 247 ms 1920 KB WA in grader: NO
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Correct 0 ms 384 KB correct
3 Incorrect 191 ms 4728 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 384 KB correct
3 Correct 1 ms 384 KB correct
4 Correct 1 ms 384 KB correct
5 Correct 0 ms 384 KB correct
6 Correct 1 ms 384 KB correct
7 Correct 1 ms 384 KB correct
8 Correct 0 ms 384 KB correct
9 Correct 0 ms 384 KB correct
10 Correct 0 ms 384 KB correct
11 Correct 0 ms 384 KB correct
12 Correct 0 ms 384 KB correct
13 Correct 0 ms 384 KB correct
14 Correct 4 ms 384 KB correct
15 Correct 4 ms 384 KB correct
16 Correct 4 ms 472 KB correct
17 Correct 4 ms 384 KB correct
18 Correct 2 ms 384 KB correct
19 Correct 4 ms 384 KB correct
20 Correct 4 ms 384 KB correct
21 Correct 3 ms 384 KB correct
22 Correct 3 ms 436 KB correct
23 Correct 2 ms 384 KB correct
24 Correct 2 ms 384 KB correct
25 Correct 1 ms 384 KB correct
26 Correct 2 ms 384 KB correct
27 Correct 3 ms 384 KB correct
28 Correct 1 ms 384 KB correct
29 Correct 1 ms 384 KB correct
30 Correct 2 ms 384 KB correct
31 Correct 3 ms 384 KB correct
32 Correct 3 ms 384 KB correct
33 Correct 2 ms 384 KB correct
34 Incorrect 247 ms 1920 KB WA in grader: NO
35 Halted 0 ms 0 KB -