Submission #103014

#	Time	Username	Problem	Language	Result	Execution time	Memory
103014		hugo_pm	Race (IOI11_race)	C++17	100 / 100	2894 ms	90820 KiB

race

#include "race.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 int BIG = (int)(1e9);

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

const int borne = 201*1000;
const int lgb = 19;
int nbNoeuds, somVoulue;
vector<pii> adj[borne];
int anc[borne][lgb];
int se[borne][lgb];

// ROOT 
int par[borne], dep[borne], dse[borne];

void dfsInit(int nod)
{
	form2(i, 1, lgb) {
		int tmp = anc[nod][i-1];
		if (tmp == -1) anc[nod][i] = -1;
		else {
			anc[nod][i] = anc[tmp][i-1];
		}
	}
	for (pii vor : adj[nod]) if (vor.fi != anc[nod][0]) {
		int vo = vor.fi;
		anc[vo][0] = nod;
		dep[vo] = dep[nod] + 1;
		dse[vo] = dse[nod] + vor.se;
		dfsInit(vo);
	}
}

int lca(int u, int v)
{
	assert(u != -1);
	assert(v != -1);
	if (u == v) return u;

	if (dep[u] < dep[v]) return lca(v, u);
	ford(i, lgb) {
		int kc = (1 << i);
		if (dep[u] - dep[v] >= kc && anc[u][i] != -1) {
			u = anc[u][i];
		}
	}
	if (dep[u] != dep[v]) { cout << u << " " << v << endl << flush; }
	assert(dep[u] == dep[v]);

	if (u == v) return u;

	ford(i, lgb) {
		int nu = anc[u][i], nv = anc[v][i];
		if (nu != nv && nu != -1 && nv != -1) { u = nu; v = nv; }
	}

	assert(u != v);
	assert(anc[u][0] == anc[v][0]);
	return anc[u][0];
}

int nbEdges(int u, int v, int art=-1)
{
	if (art == -1)  art = lca(u, v);
	int d1 = dep[u] - dep[art];
	int d2 = dep[v] - dep[art];
	assert(d1 >= 0 && d2 >= 0);
	return d1+d2; 
}

int sumEdges(int u, int v, int art=-1)
{
	if (art == -1) art = lca(u, v);
	int d1 = dse[u] - dse[art];
	int d2 = dse[v] - dse[art];
	assert(d1 >= 0 && d2 >= 0);
	return d1+d2;
}

// Cendec

bool bloque[borne];
int cpar[borne];
int csz[borne];

void dfsInfos(int nod)
{
	csz[nod] = 1;
	for (auto vor : adj[nod]) {
		int vo = vor.fi;
		if (vo == cpar[nod] || bloque[vo]) continue;
		cpar[vo] = nod;
		dfsInfos(vo);
		csz[nod] += csz[vo];
	}
}

int findCen(int nod, int tot)
{
	int st = 0;
	int mk = -BIG, be=-1;
	for (auto vor : adj[nod]) {
		int vo = vor.fi;
		if (vo == cpar[nod] || bloque[vo]) continue;
		st += csz[vo];
		if (csz[vo] > mk) {
			mk = csz[vo];
			be = vo;
		}
	}
	int reste = tot-csz[nod];
	if (2*mk <= tot && 2*reste <= tot) {
		return nod;
	} else if (be != -1) {
		return findCen(be, tot);
	}
	return -1000;
}

vector<int> cen[borne];
int cenroot=-1;

int cenDec(int from, int vers, int tot)
{
	cpar[vers] = -1;
	dfsInfos(vers);
	int nod = findCen(vers, tot);
	assert(nod != -1000);
	if (cenroot == -1) cenroot = nod;
	bloque[nod] = true;

	int st=0;
	vector<pii> toproc;
	for (auto vor : adj[nod]) {
		int vo = vor.fi;
		if (vo == cpar[nod] || bloque[vo]) continue;
		st += csz[vo];
		toproc.push_back({vo, csz[vo]});	
	}

	if (cpar[nod] != -1) {
		int reste=tot-1-st;
		if (reste != 0) { toproc.push_back({cpar[nod], reste}); }
	}

	for (auto x : toproc) {
		int res = cenDec(nod, x.fi, x.se);
		cen[nod].push_back(res);
	}
	return nod;
}

vector<int> enfants[borne];
int rep = BIG;

void proc(int nod)
{
	enfants[nod].push_back(nod);
	unordered_map<int, int> tc;
	tc[0] = 0;
	for (int enf : cen[nod]) {
		vector<pii> wx;
		proc(enf);
		for (int x : enfants[enf]) {
			enfants[nod].push_back(x);
			int art = lca(nod, x);
			int ss = sumEdges(nod, x, art);
			int ne = nbEdges(nod, x, art);
			wx.push_back({ss,ne});
			int req = somVoulue - ss;
			if (req < 0) continue;
			auto it2 = tc.find(req);
			if (it2 != tc.end()) {
				chmin(rep, ne + it2->se);
			}
		}
		for (auto x : wx) {
			tc.insert(x);
			if (tc[x.fi] > x.se) tc[x.fi] = x.se;
		}
	}
}

int solve()
{
	anc[0][0] = -1;
	dfsInit(0);
	cenDec(-1, 0, nbNoeuds);

	proc(cenroot);
	if (rep == BIG) rep = -1;
	return rep;
}

int best_path(int N, int K, int H[][2], int L[])
{
	nbNoeuds = N;
	somVoulue = K;
	form(i, N-1) {
		int u = H[i][0], v = H[i][1];
		int p = L[i];
		adj[u].push_back({v,p});
		adj[v].push_back({u,p});
	}
	return solve();
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57