Submission #677921

#	Time	Username	Problem	Language	Result	Execution time	Memory
677921		APROHACK	Keys (IOI21_keys)	C++17	37 / 100	203 ms	27068 KiB

keys

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int n, m;
vector<pair<int, int> >puentesDeEsteColor[2005];
int colorDeNodo[2005];
int respuestaParaNodo[2005];
int menorDeTodos = INT32_MAX;


bool yaPaso[2005];
int padre[2005];
vector<int>nodosDeEsteMan[2005];
int recorriendo;

int findPadre(int u){
	if(padre[u] == u)return u;
	return padre[u] = findPadre(padre[u]);
}

queue<int>llavesPorTomar;

void unir(int u, int v){
	u = findPadre(u);
	v = findPadre(v);
	if(u==v)return;
	//cout << "vamos a unir " << u << " " << v << endl;
	if(nodosDeEsteMan[u].size()>nodosDeEsteMan[v].size())swap(u, v);
	//u -> v
	if(u == findPadre(recorriendo)){
		for(int i = 0 ; i < nodosDeEsteMan[v].size() ; i++){
			int curNodo = nodosDeEsteMan[v][i];

			llavesPorTomar.push(colorDeNodo[curNodo]);

		}
	}else if(v == findPadre(recorriendo)){
		for(int i = 0 ; i < nodosDeEsteMan[u].size() ; i++){
			int curNodo = nodosDeEsteMan[u][i];

			llavesPorTomar.push(colorDeNodo[curNodo]);

		}
	}

	for(int i = 0 ; i < nodosDeEsteMan[u].size() ; i ++){
		padre[nodosDeEsteMan[u][i]] = v;
		nodosDeEsteMan[v].pb(nodosDeEsteMan[u][i]);
	}
	nodosDeEsteMan[u].clear();


}


int recorrerDesdeNodo(int u){
	//cout << "resolviendo para " << u << endl;
	recorriendo = u;

	llavesPorTomar.push(colorDeNodo[u]);
	while(!llavesPorTomar.empty()){
		int currentColor = llavesPorTomar.front();
		llavesPorTomar.pop();
		if(yaPaso[currentColor])continue;
		yaPaso[currentColor] = true;
		//cout << "Analizando color " << currentColor << endl;

		for(pair<int, int> puente:puentesDeEsteColor[currentColor]){
			unir(puente.ff, puente.ss);
			recorriendo = findPadre(recorriendo);
			if(nodosDeEsteMan[recorriendo].size()>menorDeTodos)return nodosDeEsteMan[recorriendo].size();	
		}
	}
	return nodosDeEsteMan[recorriendo].size();
}

void reiniciar(){
	memset(yaPaso, false, sizeof yaPaso);
	for(int i = 0 ; i < n ; i ++){
		padre[i] = i;
		nodosDeEsteMan[i].clear();
		nodosDeEsteMan[i].pb(i);
	}

	while(!llavesPorTomar.empty())llavesPorTomar.pop();

}


std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = r.size();
	m = u.size();
	for(int i = 0 ; i < m ; i ++){
		puentesDeEsteColor[c[i]].pb({u[i], v[i]});
	}
	for(int i = 0 ; i <n ; i ++){
		colorDeNodo[i] = r[i];
	}
	vector<int>ans;
	for(int i = 0 ; i <n ; i ++){

		reiniciar();
		respuestaParaNodo[i] = recorrerDesdeNodo(i);
		
		menorDeTodos=min(respuestaParaNodo[i], menorDeTodos);

		//cout << "Respuesta para nodo " << i << " = " << respuestaParaNodo[i] << endl;
		
	}
	for(int i = 0 ; i < n ; i ++){
		if(respuestaParaNodo[i] == menorDeTodos)ans.pb(1);
		else ans.pb(0);
	}
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void unir(int, int)':
keys.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 0 ; i < nodosDeEsteMan[v].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
keys.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for(int i = 0 ; i < nodosDeEsteMan[u].size() ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
keys.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i = 0 ; i < nodosDeEsteMan[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
keys.cpp: In function 'int recorrerDesdeNodo(int)':
keys.cpp:74:41: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |    if(nodosDeEsteMan[recorriendo].size()>menorDeTodos)return nodosDeEsteMan[recorriendo].size();
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33