Submission #1067634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067634		oscar1f	Keys (IOI21_keys)	C++17	37 / 100	190 ms	87116 KiB

keys

#include<bits/stdc++.h>
using namespace std;

const int TAILLE_MAX=300*1000+5;
int nbSom,nbAre,nbCompo;
int clef[TAILLE_MAX];
int taille[TAILLE_MAX];
set<int> listeDispo[TAILLE_MAX];
vector<pair<int,int>> adjaInit[TAILLE_MAX];
int pere[TAILLE_MAX];
vector<int> somInter,ordre;
int numCompo[TAILLE_MAX];
int dv[TAILLE_MAX];
vector<int> adja[TAILLE_MAX],adjaTrans[TAILLE_MAX];
vector<int> listeCompo[TAILLE_MAX];
int atteign[TAILLE_MAX];

int find(int pos) {
	if (pos!=pere[pos]) {
		pere[pos]=find(pere[pos]);
	}
	return pere[pos];
}

void DFS1(int pos) {
	if (dv[pos]==0) {
		dv[pos]=1;
		for (int i:adja[pos]) {
			DFS1(i);
		}
		ordre.push_back(pos);
	}
}

void DFS2(int pos) {
	if (numCompo[pos]==0) {
		numCompo[pos]=nbCompo;
		listeCompo[nbCompo].push_back(pos);
		for (int i:adjaTrans[pos]) {
			DFS2(i);
		}
	}
}

int dyna(int pos) {
	if (atteign[pos]!=0) {
		return atteign[pos];
	}
	atteign[pos]=taille[pos];
	set<int> listeAtteign;
	for (int i:adja[pos]) {
		listeAtteign.insert(find(i));
	}
	for (int i:listeAtteign) {
		atteign[pos]+=dyna(i);
	}
	return atteign[pos];
}

void calcAdja() {
	somInter.clear(); 
	for (int i=0;i<nbSom;i++) {
		adja[i].clear();
		adjaTrans[i].clear();
		if (find(i)==i) {
			somInter.push_back(i);
			numCompo[i]=0;
			dv[i]=0;
			atteign[i]=0;
		}
	}
	for (int i=0;i<nbSom;i++) {
		for (auto j:adjaInit[i]) {
			if ((*listeDispo[find(i)].lower_bound(j.second))==j.second and find(i)!=find(j.first)) {
				//cout<<find(i)<<" "<<find(j.first)<<endl;
				adja[find(i)].push_back(find(j.first));
				adjaTrans[find(j.first)].push_back(find(i));
			}
		}
	}
}

vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c) {
	nbSom=r.size();
	nbAre=c.size();
	for (int i=0;i<nbSom;i++) {
		clef[i]=r[i];
		pere[i]=i;
		taille[i]=1;
		listeDispo[i].insert(clef[i]);
	}
	for (int i=0;i<nbAre;i++) {
		adjaInit[u[i]].push_back({v[i],c[i]});
		adjaInit[v[i]].push_back({u[i],c[i]});
	}	
	int modif=1,posMax=0,valMax,plusPetit;
	while (modif==1) {
		/*cout<<"NOUVEAU"<<endl;
		for (int i=0;i<nbSom;i++) {
			cout<<find(i)<<" ";
		}
		cout<<endl;*/
		calcAdja();
		ordre.clear();
		for (int i:somInter) {
			DFS1(i);
		}
		reverse(ordre.begin(),ordre.end());
		nbCompo=0;
		for (int i:ordre) {
			if (numCompo[i]==0) {
				nbCompo++;
				listeCompo[nbCompo].clear();
				DFS2(i);
			}
		}
		modif=0;
		somInter.clear();
		for (int i=1;i<=nbCompo;i++) {
			/*cout<<i<<" : ";
			for (int j:listeCompo[i]) {
				cout<<j<<" ";
			}
			cout<<endl;*/
			if ((int)listeCompo[i].size()>1) {
				modif=1;
				valMax=0;
				for (int j:listeCompo[i]) {
					if (taille[j]>valMax) {
						valMax=taille[j];
						posMax=j;
					}
				}
				somInter.push_back(posMax);
				for (int j:listeCompo[i]) {
					if (j!=posMax) {
						taille[posMax]+=taille[j];
						pere[j]=posMax;
						for (int k:listeDispo[j]) {
							listeDispo[posMax].insert(k);
						}
						for (int k:adja[j]) {
							adja[posMax].push_back(k);
						}
					}
				}
			}
			else {
				somInter.push_back(listeCompo[i][0]);
			}
		}
		plusPetit=TAILLE_MAX;
		for (int i:somInter) {
			atteign[i]=dyna(i);
			plusPetit=min(plusPetit,atteign[i]);
		}
		if (modif==1) {
			modif=0;
			for (int i:somInter) {
				if (atteign[i]==plusPetit and ((int)listeCompo[numCompo[i]].size()>1 or taille[i]<plusPetit)) {
					modif=1;
				}
			}
		}	
	}
	vector<int> rep;
	for (int i=0;i<nbSom;i++) {
		atteign[i]=atteign[find(i)];
		if (atteign[i]==plusPetit) {
			rep.push_back(1);
		}
		else {
			rep.push_back(0);
		}
	}
	return rep;
}

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