Submission #806874

#	Time	Username	Problem	Language	Result	Execution time	Memory
806874		oscar1f	Mergers (JOI19_mergers)	C++17	100 / 100	1066 ms	117864 KiB

mergers

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

//#define int long long

const int MAX_SOM=500*1000+5,MAX_LOG=20;
int nbSom,nbGroupe,deb,fin,nbCompo,rep;
vector<int> adja[MAX_SOM];
int nbOccu[MAX_SOM],numGroupe[MAX_SOM],pere[MAX_SOM][MAX_LOG],numCompo[MAX_SOM];
int nbVois[MAX_SOM];
int lcaGroupe[MAX_SOM];
int prof[MAX_SOM];
int cumu[MAX_SOM];
vector<pair<int,int>> listeAre;

void marque(int pos,int idCompo) {
	numCompo[pos]=idCompo;
	for (int i:adja[pos]) {
		if (i!=pere[pos][0] and numCompo[i]==0) {
			marque(i,idCompo);
		}
	}
}

void DFS(int pos,int anci) {
	pere[pos][0]=anci;
	prof[pos]=prof[pere[pos][0]]+1;
	for (int i:adja[pos]) {
		if (i!=pere[pos][0]) {
			DFS(i,pos);
		}
	}
}

int calcLca(int som1,int som2) {
	if (prof[som1]>prof[som2]) {
		swap(som1,som2);
	}
	for (int i=MAX_LOG-1;i>=0;i--) {
		if (prof[pere[som2][i]]>=prof[som1]) {
			som2=pere[som2][i];
		}
	}
	if (som1==som2) {
		return som1;
	}
	for (int i=MAX_LOG-1;i>=0;i--) {
		if (pere[som1][i]!=pere[som2][i]) {
			som1=pere[som1][i];
			som2=pere[som2][i];
		}
	}
	return pere[som1][0];
}

void DFS2(int pos) {
	for (int i:adja[pos]) {
		if (i!=pere[pos][0]) {
			DFS2(i);
			cumu[pos]+=cumu[i];
		}
	} 
	if (cumu[pos]==0) {
		nbCompo++;
		marque(pos,nbCompo);
	}
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>nbSom>>nbGroupe;
	for (int i=1;i<nbSom;i++) {
		cin>>deb>>fin;
		adja[deb].push_back(fin);
		adja[fin].push_back(deb);
		listeAre.push_back({deb,fin});
	}
	DFS(1,0);
	for (int j=1;j<MAX_LOG;j++) {
		for (int i=1;i<=nbSom;i++) {
			pere[i][j]=pere[pere[i][j-1]][j-1];
		}
	}
	for (int i=1;i<=nbSom;i++) {
		cin>>numGroupe[i];
		numGroupe[i]--;
		nbOccu[numGroupe[i]]++;
		if (nbOccu[numGroupe[i]]==1) {
			lcaGroupe[numGroupe[i]]=i;
		}
		else {
			lcaGroupe[numGroupe[i]]=calcLca(lcaGroupe[numGroupe[i]],i);
		}
	}
	for (int i=1;i<=nbSom;i++) {
		cumu[i]++;
		cumu[lcaGroupe[numGroupe[i]]]--;
	}
	DFS2(1);
	for (auto j:listeAre) {
		deb=j.first;
		fin=j.second;
		if (numCompo[deb]!=numCompo[fin]) {
			nbVois[numCompo[deb]]++;
			nbVois[numCompo[fin]]++;
		}
	}
	/*cout<<nbCompo<<endl;
	for (int i=1;i<=nbSom;i++) {
		cout<<i<<" : "<<numCompo[i]<<endl;
	}*/
	for (int i=1;i<=nbCompo;i++) {
		if (nbVois[i]==1) {
			rep++;
		}
	}
	if (rep==1) {
		cout<<0<<endl;
	}
	else {
		cout<<(rep+1)/2<<endl;
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30