Submission #834901

#	Time	Username	Problem	Language	Result	Execution time	Memory
834901		oscar1f	Split the Attractions (IOI19_split)	C++17	100 / 100	73 ms	13944 KiB

split

#include<bits/stdc++.h>
#include "split.h"

using namespace std;

const int MAX_SOM=100*1000+5;
int nbSom,nbAre,somPere,autreCompo,trouve,reste;
vector<int> rep;
vector<pair<int,int>> obj;
vector<int> adja[MAX_SOM];
int dv[MAX_SOM];
int prof[MAX_SOM];
int interdit[MAX_SOM];

int DFS(int pos) {
	if (prof[pos]==0) {
		prof[pos]=1;
		for (int i:adja[pos]) {
			prof[pos]+=DFS(i);
		}
		//cout<<pos<<" "<<prof[pos]<<endl;
		return prof[pos];
	}
	return 0;
}

int calcDeb(int pos) {
	for (int i:adja[pos]) {
		if (prof[i]<prof[pos] and prof[i]>=obj[0].first) {
			return calcDeb(i);
		}
	}
	return pos;
}

void trouveMonte(int pos) {
	if (dv[pos]==0) {
		dv[pos]=1;
		for (int i:adja[pos]) {
			if (prof[i]>prof[somPere]) {
				trouve=1;
			}
			else if (prof[i]<prof[pos]) {
				trouveMonte(i);
			}
		}
	}
}

void prop1(int pos) {
	if (reste>0 and interdit[pos]==0 and rep[pos]==0) {
		rep[pos]=obj[0].second;
		reste--;
		for (int i:adja[pos]) {
			if (prof[i]<prof[pos]) {
				prop1(i);
			}
		}
	}
}

void prop2(int pos) {
	if (reste>0 and rep[pos]==0) {
		rep[pos]=obj[1].second;
		reste--;
		for (int i:adja[pos]) {
			prop2(i);
		}
	}
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
	nbSom=n;
	nbAre=p.size();
	obj={{a,1},{b,2},{c,3}};
	sort(obj.begin(),obj.end());
	rep.resize(nbSom);
	for (int i=0;i<nbAre;i++) {
		adja[p[i]].push_back(q[i]);
		adja[q[i]].push_back(p[i]);
	}
	somPere=DFS(0);
	somPere=calcDeb(0);
	autreCompo=nbSom-prof[somPere];
	//cout<<somPere<<endl;
	for (int i:adja[somPere]) {
		if (prof[i]<prof[somPere] and autreCompo<obj[0].first) {
			trouve=0;
			trouveMonte(i);
			if (trouve==1) {
				//cout<<i<<" ";
				interdit[i]=1;
				autreCompo+=prof[i];
			}
		}
	}
	//cout<<endl;
	if (autreCompo<obj[0].first) {
		return rep;
	}
	if (autreCompo<obj[1].first) {
		swap(obj[0],obj[1]);
	}
	reste=obj[0].first;
	prop1(somPere);
	reste=obj[1].first;
	prop2(0);
	for (int i=0;i<nbSom;i++) {
		if (rep[i]==0) {
			rep[i]=obj[2].second;
		}
	}
	return rep;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36