Submission #109248

#	Time	Username	Problem	Language	Result	Execution time	Memory
109248		hugo_pm	Mergers (JOI19_mergers)	C++17	100 / 100	1762 ms	81400 KiB

mergers

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

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 1000*1000 + 15;
int nbNoeuds, nbAretes, nbGroupes;
stack<int> dfsPile;

pii noeudsArete[borne];
vector<int> adjAr[borne];

int voisin(int ar, int nod)
{
	pii arete = noeudsArete[ar];

	if (arete.fi == nod) return arete.se;
	else { return arete.fi; }
}

int dfsNum[borne], dfsLow[borne];
int arFrom[borne];
bitset<borne> estPont;
int curTemps = 0;

void dfsTarjan(int dep)
{
	dfsPile.push(dep);
	while (!dfsPile.empty()) {
		int nod = dfsPile.top();
		dfsPile.pop();
		if (dfsNum[nod] == 0) {
			dfsPile.push(nod);

			dfsNum[nod] = ++curTemps;
			dfsLow[nod] = dfsNum[nod];
			for (int arete : adjAr[nod]) {
				int vo = voisin(arete, nod);
				if (dfsNum[vo] > 0 && arete != arFrom[nod]) {
					chmin(dfsLow[nod], dfsLow[vo]);
				}
				if (dfsNum[vo] == 0) {
					arFrom[vo] = arete;
					if (nod == noeudsArete[arete].se) swap(noeudsArete[arete].fi, noeudsArete[arete].se);
					dfsPile.push(vo);
				}
			}

		} else {
			for (int arete : adjAr[nod]) {
				int vo = voisin(arete, nod);
				if (arFrom[vo] == arete) {
					chmin(dfsLow[nod], dfsLow[vo]);
				}
			}
		}
	}	
}

void finaliserPonts()
{
	form(i, nbAretes) {
		if (dfsNum[noeudsArete[i].fi] < dfsLow[noeudsArete[i].se]) estPont[i] = true;
	}
}

//vector<int> bridgeTree[borne];
char degBT[borne];

int nbComp = 0;
int indComp[borne];
bool vuFinaliser[borne];
int lst[borne];

void compresser(int dep)
{
	dfsPile.push(dep);
	indComp[dep] = nbComp;
	while (! dfsPile.empty()) {
		int nod = dfsPile.top();
		dfsPile.pop();

		for (int arete : adjAr[nod]) if (!estPont[arete]) {
			int vo = voisin(arete, nod);
			if (indComp[vo] == -1) {
				indComp[vo] = nbComp;
				dfsPile.push(vo);
			}
		}
	}
}

void finaliser(int dep)
{
	stack<int> dfsPile;
	dfsPile.push(dep);
	vuFinaliser[dep] = true;

	while (!dfsPile.empty()) {
		int nod = dfsPile.top();
		dfsPile.pop();

		int maComp = indComp[nod];
		for (int arete : adjAr[nod]) if (estPont[arete]) {
			int voRaw = voisin(arete, nod);
			int voComp = indComp[voRaw];
			if (lst[voComp] == maComp) continue;
			lst[voComp] = maComp;

			//bridgeTree[maComp].push_back(voComp);
			if (degBT[maComp] < 2) ++degBT[maComp];
			// Ajouté dans l'autre sens lors de la finalisation de voComp
		}

		for (int arete : adjAr[nod]) {
			if (!estPont[arete]) {
				int vo = voisin(arete, nod);
				if (!vuFinaliser[vo]) {
					vuFinaliser[vo] = true;
					dfsPile.push(vo);
				}
			}
		}
	}
}

int lstGroupe[borne];

void solve()
{
	fill_n(&indComp[0], borne, -1);
	fill_n(&lst[0], borne, -1);
	fill_n(&lstGroupe[0], borne, -1);

	cin >> nbNoeuds >> nbGroupes;
	nbAretes = nbNoeuds-1;
	form(i, nbAretes) {
		int u, v; cin >> u >> v; --u; --v;
		noeudsArete[i] = {u,v};
		adjAr[u].push_back(i);
		adjAr[v].push_back(i);
	}

	form(nod, nbNoeuds) {
		int groupe; cin >> groupe; --groupe;
		if (lstGroupe[groupe] != -1) {
			int prev = lstGroupe[groupe];

			noeudsArete[nbAretes] = {nod, prev};
			adjAr[nod].push_back(nbAretes);
			adjAr[prev].push_back(nbAretes);
			++nbAretes;
		}
		lstGroupe[groupe] = nod;
	}

	arFrom[0] = -1;
	dfsTarjan(0);
	finaliserPonts();

	form(nod, nbNoeuds) if (indComp[nod] == -1) {
		compresser(nod);
		++nbComp;
	}

	form(nod, nbNoeuds) if (!vuFinaliser[nod]) finaliser(nod);

	int nbFeuilles = 0;
	form(nod, nbComp) {
		//int deg = bridgeTree[nod].size();
		int deg = degBT[nod];
		if (deg == 1) ++nbFeuilles;
	}
	cout << (nbFeuilles+1) / 2 << "\n";
}

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