Submission #770093

#	Time	Username	Problem	Language	Result	Execution time	Memory
770093		APROHACK	Simurgh (IOI17_simurgh)	C++14	51 / 100	119 ms	5116 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define nxt first
#define idx second
#define ff first
#define ss second
using namespace std;
int nodes, edjes;
vector<pair<int, int> >adj[501];
vector<pair<int, int > >ejes;
vector<int>indicesAns, otros;
vector<int>posibles;
int hoja;
bool yaSeSabia[500*500];
bool checked[501];
int contC = 0;
int repre[501];
int ultimoEje;
//bool vis[501];

void memss(){
	//for(int i = 0 ; i < nodes; i ++)vis[i] = false;
}

int findd(int nod){
	if(repre[nod] == nod)return nod;
	return repre[nod] = findd(repre[nod]);
}

void joinn(int a, int b){
	a = findd (a);
	b = findd (b);
	if(a==b)return;
	repre[a] = b;
}

void unir(){
	int used = 0;
	//cout << " nuevo arbol " << endl;
	otros.clear();
	posibles.clear();
	hoja = -1;
	for(int i = 0 ; i < nodes ; i ++)repre[i] = i;
	
	for(int i = 0 ; i < indicesAns.size() ; i ++){
		used ++ ;
		joinn(ejes[indicesAns[i]].ff, ejes[indicesAns[i]].ss);
		//cout << ejes[indicesAns[i]].ff << " join " << ejes[indicesAns[i]].ss << endl;
		
	}
	
	ultimoEje = -1;
	for(int i = 0 ; i < edjes ; i ++){
		if(findd (ejes[i].ff) == findd(ejes[i].ss)){
			yaSeSabia[i] = true;
		}
	}
	for(int i = 0 ; i < edjes ; i ++){
		if(findd (ejes[i].ff) != findd(ejes[i].ss)){
			if(used < nodes-2){
			used ++ ;
			otros.pb(i);
			joinn(ejes[i].ff, ejes[i].ss);
			//cout << ejes[i].ff << " join " << ejes[i].ss << endl;
			hoja = checked[ejes[i].ss] ? ejes[i].ff : ejes[i].ss;
			}else{
				posibles.pb(i);
			}
		}
	}
}

int calculate(vector<pair<int, int> >&resp){
	//cout << "probando para " << k << endl;
	vector<int>indTest;
	indTest = indicesAns;
	for(auto i : otros)indTest.pb(i);
	int maxi = INT_MIN;
	for(int i = 0 ; i < posibles.size() ; i ++){
		if(yaSeSabia[posibles[i]])continue;
		indTest.pb(posibles[i]);
		yaSeSabia[posibles[i]] = true;
		resp.pb({posibles[i], count_common_roads( indTest )});
		indTest.pop_back();
		maxi = max(maxi, resp.back().ss);
	}
	return maxi;// Ya calcule si estos ejes son o no de la respuesta.
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	for(int i = 0 ; i < n; i ++)checked[i] = false;
	for(int i = 0 ; i < u.size() ; i ++){
		yaSeSabia[i] = false;
	}
	nodes = n;
	edjes = u.size();
	for(int i = 0 ; i < edjes ; i ++){
		adj[u[i]].pb({v[i], i});
		adj[v[i]].pb({u[i], i});
		ejes.pb({u[i], v[i]});
	}
	memss();
	
	while(contC < n){
		unir();
		vector<pair<int, int> >resp;
		int maxi = calculate(resp);
		if(maxi == -1)break;
		//cout << " gold " << endl;
		for(auto i : resp){
			if(i.ss == maxi){
				//cout << i.ff << endl;
				indicesAns.pb(i.ff);
			}
		}
		if(indicesAns.size() == n-1)return indicesAns;
	}
	
	
	return indicesAns;
}

Compilation message (stderr)

simurgh.cpp: In function 'void unir()':
simurgh.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 0 ; i < indicesAns.size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int calculate(std::vector<std::pair<int, int> >&)':
simurgh.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i = 0 ; i < posibles.size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i = 0 ; i < u.size() ; i ++){
      |                  ~~^~~~~~~~~~
simurgh.cpp:118:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |   if(indicesAns.size() == n-1)return indicesAns;
      |      ~~~~~~~~~~~~~~~~~~^~~~~~

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