Submission #435022

#	Time	Username	Problem	Language	Result	Execution time	Memory
435022		Arturgo	Keys (IOI21_keys)	C++17	9 / 100	369 ms	47780 KiB

keys

#include <vector>
#include <iostream>
#include <set>
using namespace std;

int nbPieces, nbRoutes;
vector<int> ordre;
vector<int> parents[300 * 1000];

int curPasse;
int derPasse[300 * 1000];

int curDate;
int date[300 * 1000];

void dfs(int piece) {
	if(derPasse[piece] == curPasse)
		return;
	derPasse[piece] = curPasse;
	
	for(int parent : parents[piece])
		dfs(parent);
	
	ordre.push_back(piece);
}

bool cles[300 * 1000];
vector<int> sommetsVus[300 * 1000];
vector<int> aNettoyer;

vector<int> c, r;

vector<pair<int, int>> voisins[300 * 1000];

int minNbVus = 1000 * 1000 * 1000;
vector<int> reponse;

void explore(int piece) {
	vector<int> sommetsOks;
	sommetsOks.push_back(piece);
	
	bool accedeAutre = false;
	vector<int> vus;
	
	curDate++;
	
	while(!sommetsOks.empty()) {
		int sommet = sommetsOks.back();
		sommetsOks.pop_back();
		
		if(date[sommet] == curDate)
			continue;
		if(date[sommet] != 0) {
			accedeAutre = true;
			continue;
		}
		
		vus.push_back(sommet);
		date[sommet] = curDate;
		
		cles[r[sommet]] = true;
		aNettoyer.push_back(r[sommet]);
		
		for(int sommet : sommetsVus[c[sommet]]) {
			sommetsOks.push_back(sommet);
		}
		sommetsVus[c[sommet]].clear();
		
		for(pair<int, int> voisin : voisins[sommet]) {
			if(cles[voisin.second])
				sommetsOks.push_back(voisin.first);
			else {
				sommetsVus[voisin.second].push_back(voisin.first);
				aNettoyer.push_back(voisin.second);
			}
		}
	}
	
	while(!aNettoyer.empty()) {
		int pos = aNettoyer.back();
		aNettoyer.pop_back();
		sommetsVus[pos].clear();
		cles[pos] = false;
	}
	
	if(accedeAutre)
		return;
	
	if(vus.size() < minNbVus) {
		minNbVus = vus.size();
		reponse.clear();
	}
	if(vus.size() == minNbVus) {
		for(int vu : vus) {
			reponse.push_back(vu);
		}
	}
}

vector<int> find_reachable(vector<int> _r, vector<int> u, vector<int> v, vector<int> _c) {
	c = _c;
	r = _r;
	int nbPieces = r.size();
	int nbRoutes = u.size();
	
	for(int iRoute = 0;iRoute < nbRoutes;iRoute++) {
		if(c[iRoute] == r[u[iRoute]])
			parents[v[iRoute]].push_back(u[iRoute]);
		if(c[iRoute] == r[v[iRoute]])
			parents[u[iRoute]].push_back(v[iRoute]);
		voisins[u[iRoute]].push_back({v[iRoute], c[iRoute]});
		voisins[v[iRoute]].push_back({u[iRoute], c[iRoute]});
	}
	
	curPasse++;
	for(int iPiece = 0;iPiece < nbPieces;iPiece++) {
		dfs(iPiece);
	}
	
	while(!ordre.empty()) {
		int piece = ordre.back();
		ordre.pop_back();
		explore(piece);
	}
	
	vector<int> ans(nbPieces, 0);
	
	for(int x : reponse)
		ans[x] = 1;
	
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void explore(int)':
keys.cpp:89:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |  if(vus.size() < minNbVus) {
      |     ~~~~~~~~~~~^~~~~~~~~~
keys.cpp:93:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |  if(vus.size() == minNbVus) {
      |     ~~~~~~~~~~~^~~~~~~~~~~

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