oj.uz

Submission #108178

# Submission time Handle Problem Language Result Execution time Memory
108178 2019-04-27T23:29:01 Z hugo_pm Highway Tolls (IOI18_highway) C++17
51 / 100
 259 ms 21940 KB 
#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];
int profondeurArete[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);
		profondeurArete[arete] = dep;
		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;

vector<pii> recyclage;

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;

	if (hauteur) {
		for (pii info : recyclage) {
			int m = info.fi, cnt = info.se;
			if (! (l < m && m < r)) continue;
			ajuster(deb, m);
			int requis = dist;
			requis -= (ivFin - m);
			assert(cnt <= requis);
			if (cnt == requis) r = m;
			else l = m+1;
		}
	}

	while (l < r) {
		int m = (l+r) / 2;
		ajuster(deb, m);
		int requis = dist;
		if (hauteur) { requis -= (ivFin - m); }
		int cnt = countAretes();
		if (hauteur == 0) { recyclage.push_back({m, cnt}); } 
		assert(cnt <= requis);

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

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

}

pair<int, int> deuxAretes(int niv, int excp=-1)
{
	assert(excp != -2);
	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;

	if (excp != -1) --totSurNiv;

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

	if (totSurNiv == 1 || excp != -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};
}

int corresp[borne];

void remonter(int nod, int ha)
{
	form(i, ha) {
		corresp[profondeurArete[arPar[nod]]] = arPar[nod];
		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) {
	form(i, borne) corresp[i] = -2;

	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);
	}
	form(i, nbLevels) {
		random_shuffle(niveaux[i].begin(), niveaux[i].end());
	}

	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;
	}

	int newFin = ivDeb + (dist-hauteur) - 1;
	assert(newFin < ivFin);
	ajuster(ivDeb, newFin);

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

	answer(s1,s2);

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6956 KB Output is correct
2 Correct 8 ms 7008 KB Output is correct
3 Correct 8 ms 7088 KB Output is correct
4 Correct 8 ms 6952 KB Output is correct
5 Correct 8 ms 6952 KB Output is correct
6 Correct 8 ms 7052 KB Output is correct
7 Correct 8 ms 7004 KB Output is correct
8 Correct 8 ms 7032 KB Output is correct
9 Correct 8 ms 7092 KB Output is correct
10 Correct 8 ms 6932 KB Output is correct
11 Correct 8 ms 6908 KB Output is correct
12 Correct 8 ms 6904 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7032 KB Output is correct
2 Correct 28 ms 7784 KB Output is correct
3 Correct 219 ms 13948 KB Output is correct
4 Correct 176 ms 14072 KB Output is correct
5 Correct 223 ms 13968 KB Output is correct
6 Correct 196 ms 14016 KB Output is correct
7 Correct 213 ms 14080 KB Output is correct
8 Correct 189 ms 14028 KB Output is correct
9 Correct 209 ms 14144 KB Output is correct
10 Correct 189 ms 14020 KB Output is correct
11 Correct 231 ms 16208 KB Output is correct
12 Correct 222 ms 17200 KB Output is correct
13 Correct 203 ms 16200 KB Output is correct
14 Correct 219 ms 16684 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8612 KB Output is correct
2 Correct 42 ms 10216 KB Output is correct
3 Correct 61 ms 11928 KB Output is correct
4 Correct 134 ms 21868 KB Output is correct
5 Correct 164 ms 21940 KB Output is correct
6 Correct 160 ms 21900 KB Output is correct
7 Correct 165 ms 21812 KB Output is correct
8 Correct 167 ms 21864 KB Output is correct
9 Correct 177 ms 21800 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7032 KB Output is correct
2 Correct 28 ms 7672 KB Output is correct
3 Correct 146 ms 12480 KB Output is correct
4 Correct 166 ms 13976 KB Output is correct
5 Correct 175 ms 13984 KB Output is correct
6 Correct 201 ms 14080 KB Output is correct
7 Correct 194 ms 14068 KB Output is correct
8 Correct 215 ms 14076 KB Output is correct
9 Correct 227 ms 14112 KB Output is correct
10 Correct 198 ms 13996 KB Output is correct
11 Correct 216 ms 15888 KB Output is correct
12 Correct 259 ms 16960 KB Output is correct
13 Correct 230 ms 17464 KB Output is correct
14 Correct 225 ms 17436 KB Output is correct
15 Correct 195 ms 14060 KB Output is correct
16 Correct 195 ms 14072 KB Output is correct
17 Correct 228 ms 16960 KB Output is correct
18 Correct 212 ms 17096 KB Output is correct
19 Correct 185 ms 14024 KB Output is correct
20 Correct 216 ms 16576 KB Output is correct
21 Correct 180 ms 14360 KB Output is correct
22 Correct 171 ms 14352 KB Output is correct
23 Correct 193 ms 14484 KB Output is correct
24 Correct 197 ms 15820 KB Output is correct
25 Correct 225 ms 19536 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 14328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 14328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -