Submission #108177

#	Time	Username	Problem	Language	Result	Execution time	Memory
108177		hugo_pm	Highway Tolls (IOI18_highway)	C++17	18 / 100	235 ms	20132 KiB

highway

#include "highway.h"
#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;

const int borne = 131*1000;
int nbNoeuds, nbAretes;
int petitCout, grosCout;

vector<int> adjAr[borne]; // Indices des ARETES
int somAr[borne]; // u+v
pii noeudsAr[borne];
vector<int> niveaux[borne];
int nbLevels = 0;
int dist = 0;
int rac = 0;
int arPar[borne];
bool interdir[borne];

void dfs(int nod, int par, int dep)
{
	for (int arete : adjAr[nod]) {
		int voisin = somAr[arete] - nod;
		if (voisin == par) { arPar[nod] = arete; continue; }
		// Ici, on ordonne parent -> enfant
		if (noeudsAr[arete].fi != nod) swap(noeudsAr[arete].fi, noeudsAr[arete].se);
		niveaux[dep].push_back(arete);
		chmax(nbLevels, dep+1);
		dfs(voisin, nod, dep+1);
	}
}

vector<int> pris;
int curLeft, curRight;

void rebuild(int l1, int l2)
{
	curLeft = l1; curRight = l2;
	pris.assign(nbAretes, 0);
	form2(lvl, l1, l2+1) {
		for (int x : niveaux[lvl]) {
			pris[x] = 1;
		}
	}
}

inline void _setNiv(int niv, int val)
{
	for (int x : niveaux[niv]) pris[x] = val;
}

void ajuster(int l1, int l2)
{
	while (curLeft > l1) { // On ajoute le précedent
		--curLeft;
		_setNiv(curLeft, 1);
	}
	while (curLeft < l1) { // On supprime le courant
		_setNiv(curLeft, 0);
		++curLeft;
	}

	while (curRight < l2) { // On ajoute le suivant
		++curRight;
		_setNiv(curRight, 1);
	}
	while (curRight > l2) { // On supprime le courant
		_setNiv(curRight, 0);
		--curRight;
	}
}

int countAretes()
{
	ll cx = ask(pris);
	ll diffTot = cx - (ll)(dist) * petitCout;
	int diffUnit = (int)(diffTot / (ll)(grosCout - petitCout));
	assert(cx >= diffTot && diffUnit <= dist);
	return diffUnit;
}

int hauteur = 0, ivDeb = 0, ivFin = 0;

void construireIntervalle()
{
	if (hauteur == 0) {
		int l = curLeft, r = curRight;
		while (l < r) {
			int m = (l+r+1)/2;
			ajuster(m, curRight);
			if (countAretes() == dist) l = m;
			else r = m-1;
		}

		int deb = l;	
		ajuster(deb, curRight);
	}

	if (hauteur) rebuild(ivDeb, ivFin);
	int deb = curLeft;
	int l = curLeft, r = curRight;
	while (l < r) {
		int m = (l+r) / 2;
		ajuster(deb, m);
		int requis = dist;
		if (hauteur) { requis -= (ivFin - m); }
		int cnt = countAretes();
		assert(cnt <= requis);

		if (cnt == requis) r = m;
		else l = m+1;
	}

	assert(deb == curLeft);
	rebuild(deb, l);

}

pair<int, int> deuxAretes(int niv)
{
	rebuild(niv, niv);
	int totSurNiv = countAretes();
	assert(totSurNiv == 1 || totSurNiv == 2);

	auto &liste = niveaux[niv];
	int sz = liste.size();
	int l = 0, r = sz-1;

	while (l < r) {
		int m = (l+r+1)/2;
		_setNiv(niv, 0);
		form2(i, m, sz) pris[liste[i]] = 1;
		if (countAretes() == totSurNiv) l = m;
		else r = m-1;
	}
	int a1 = liste[l];

	if (totSurNiv == 1) { return pii {a1, -1}; }

	int relDeb = l;
	r = sz-1;
	while (l < r) {
		int m = (l+r) / 2;
		_setNiv(niv, 0);
		form2(i, relDeb, m+1) pris[liste[i]] = 1;
		if (countAretes() == totSurNiv) r = m;
		else l = m+1;
	}

	int a2 = liste[l];

	return pii {a1, a2};
}

void remonter(int nod, int ha)
{
	form(i, ha) {
		interdir[arPar[nod]] = true;
		int vx = noeudsAr[arPar[nod]].fi;
		assert(nod != vx);
		nod = vx;
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	nbNoeuds = N;
	nbAretes = U.size();
	assert(nbAretes == nbNoeuds-1);

	petitCout = A; grosCout = B;

	pris.assign(nbAretes, 0);

	form(i, nbAretes) {
		somAr[i] = U[i] + V[i];
		noeudsAr[i] = {U[i], V[i]};
		adjAr[U[i]].push_back(i);
		adjAr[V[i]].push_back(i);
	}

	rac = nbNoeuds/3;
	if (rac) --rac;

	dfs(rac, -1, 0);
	rebuild(0, nbLevels-1);
	dist = (int)(ask(pris) / (ll)(B));

	hauteur = 0;

	construireIntervalle();
	hauteur = (curRight - curLeft) + 1;
	assert(hauteur <= dist);

	ivDeb = curLeft;
	ivFin = curRight;

	rebuild(ivFin, ivFin);
	pii aretes = deuxAretes(ivFin);
	int s1 = noeudsAr[aretes.fi].se;
	remonter(s1, hauteur);

	if (aretes.se != -1) {
		int s2 = noeudsAr[aretes.se].se;
		answer(s1, s2);
		return;
	}
	
	if (hauteur == dist) {
		pii wls = deuxAretes(ivDeb);
		int s2 = noeudsAr[wls.fi].fi; // Parent lca
		assert(wls.se == -1);

		answer(s1, s2);
		return;
	}

	construireIntervalle();
	assert(curRight < ivFin);

	pii wls = deuxAretes(curRight);
	if (interdir[wls.fi]) swap(wls.fi, wls.se);
	assert(wls.fi != -1 && interdir[wls.fi] == false && wls.se != -1 && interdir[wls.se] == true);
	int s2 = noeudsAr[wls.fi].se;

	answer(s1,s2);

}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31