Submission #770075

#	Time	Username	Problem	Language	Result	Execution time	Memory
770075		APROHACK	Simurgh (IOI17_simurgh)	C++14	0 / 100	0 ms	212 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;
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(){
	//cout << " nuevo arbol " << endl;
	otros.clear();
	hoja = -1;
	for(int i = 0 ; i < nodes ; i ++)repre[i] = i;
	
	for(int i = 0 ; i < indicesAns.size() ; i ++){
		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)){
			otros.pb(i);
			ultimoEje = 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;
		}
	}
}

int calculate(vector<pair<int, int> >&resp){
	int k = hoja;
	checked[k] = true;
	//cout << "probando para " << k << endl;
	vector<int>indTest;
	indTest = indicesAns;
	if(ultimoEje == -1)return -1;
	for(auto i : otros)if(i != ultimoEje)indTest.pb(i);
	indTest.pb(ultimoEje);
	int maxi = INT_MIN;
	resp.pb({ultimoEje, count_common_roads(indTest)});
	yaSeSabia[ultimoEje] = true;
	maxi = max(maxi, resp.back().ss);
	for(int i = 0 ; i < adj[k].size() ; i ++){
		if(yaSeSabia[adj[k][i].idx])continue;
		indTest.pop_back();
		indTest.pb(adj[k][i].idx);
		yaSeSabia[adj[k][i].idx] = true;
		resp.pb({adj[k][i].idx, count_common_roads( indTest )});
		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:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 0 ; i < indicesAns.size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~
simurgh.cpp: In function 'int calculate(std::vector<std::pair<int, int> >&)':
simurgh.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i = 0 ; i < adj[k].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0 ; i < u.size() ; i ++){
      |                  ~~^~~~~~~~~~
simurgh.cpp:111:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  111 |   if(indicesAns.size() == n-1)return indicesAns;
      |      ~~~~~~~~~~~~~~~~~~^~~~~~

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