oj.uz

Submission #108177

# Submission time Handle Problem Language Result Execution time Memory
108177 2019-04-27T23:01:18 Z hugo_pm Highway Tolls (IOI18_highway) C++17
18 / 100
 235 ms 20132 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];

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6392 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 7 ms 6392 KB Output is correct
4 Correct 8 ms 6392 KB Output is correct
5 Correct 7 ms 6396 KB Output is correct
6 Correct 7 ms 6392 KB Output is correct
7 Correct 7 ms 6392 KB Output is correct
8 Correct 8 ms 6392 KB Output is correct
9 Correct 7 ms 6392 KB Output is correct
10 Correct 8 ms 6524 KB Output is correct
11 Correct 8 ms 6392 KB Output is correct
12 Correct 8 ms 6392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 28 ms 7232 KB Output is correct
3 Correct 199 ms 13092 KB Output is correct
4 Correct 177 ms 13108 KB Output is correct
5 Correct 190 ms 13100 KB Output is correct
6 Correct 207 ms 13260 KB Output is correct
7 Correct 163 ms 13168 KB Output is correct
8 Correct 190 ms 13124 KB Output is correct
9 Correct 201 ms 13176 KB Output is correct
10 Correct 222 ms 13160 KB Output is correct
11 Correct 183 ms 15076 KB Output is correct
12 Correct 235 ms 16028 KB Output is correct
13 Correct 228 ms 15124 KB Output is correct
14 Correct 226 ms 15584 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8084 KB Output is correct
2 Correct 46 ms 9484 KB Output is correct
3 Correct 67 ms 11056 KB Output is correct
4 Correct 153 ms 20132 KB Output is correct
5 Correct 148 ms 20116 KB Output is correct
6 Correct 169 ms 20100 KB Output is correct
7 Correct 198 ms 20000 KB Output is correct
8 Correct 184 ms 20032 KB Output is correct
9 Correct 167 ms 20004 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 23 ms 7232 KB Output is correct
3 Correct 124 ms 11684 KB Output is correct
4 Correct 222 ms 13128 KB Output is correct
5 Correct 220 ms 13192 KB Output is correct
6 Correct 185 ms 13128 KB Output is correct
7 Correct 204 ms 13212 KB Output is correct
8 Correct 180 ms 13184 KB Output is correct
9 Correct 197 ms 13344 KB Output is correct
10 Correct 204 ms 13136 KB Output is correct
11 Correct 211 ms 14888 KB Output is correct
12 Correct 232 ms 15824 KB Output is correct
13 Correct 227 ms 16248 KB Output is correct
14 Correct 223 ms 16168 KB Output is correct
15 Correct 212 ms 13196 KB Output is correct
16 Correct 194 ms 13236 KB Output is correct
17 Correct 228 ms 15644 KB Output is correct
18 Correct 223 ms 15896 KB Output is correct
19 Correct 194 ms 13200 KB Output is correct
20 Correct 230 ms 15504 KB Output is correct
21 Correct 171 ms 13584 KB Output is correct
22 Correct 189 ms 13588 KB Output is correct
23 Incorrect 231 ms 13628 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 13220 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 27 ms 13216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -