Submission #102978

#	Time	Username	Problem	Language	Result	Execution time	Memory
102978		hugo_pm	Race (IOI11_race)	C++17	21 / 100	3008 ms	19444 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 long long BIG = 1000000000000000000LL;

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)
{
	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];
		}
	}
	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 = 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 = lca(u, v);
	int d1 = dse[u] - dse[art];
	int d2 = dse[v] - dse[art];
	assert(d1 >= 0 && d2 >= 0);
	return d1+d2;
}

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

	int rep = (int)(1e9);
	form(i, nbNoeuds) form2(j, i+1, nbNoeuds) {
		if (sumEdges(i,j) == somVoulue) {
			chmin(rep, nbEdges(i, j));
		}
	}
	if (rep == (int)(1e9)) rep = -1;
	return rep;
}

int best_path(int N, int K, int H[][2], int L[])
{
	nbNoeuds = N;
	somVoulue = K;
	form(i, N) {
		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: 0 / 22
• Subtask 4: 0 / 57