Submission #915201

#	Time	Username	Problem	Language	Result	Execution time	Memory
915201		guilhermecpp	Race (IOI11_race)	C++17	100 / 100	1066 ms	214004 KiB

race

#include <bits/stdc++.h>
using namespace std;       
 
#define NMAX 200010
#define KMAX 1000010
#define LOGMAX 17
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< pll, ll > pplll;
typedef vector< ll > vl;
typedef vector< pll > vpll;

ll n, m;

vpll grafo[NMAX];
ll level[NMAX];

ll anc[NMAX][LOGMAX + 1];
ll dist[NMAX][LOGMAX + 1];

ll qtdCent;
ll pai[NMAX];
ll sub[NMAX];

stack< ll > ordem;

ll caso = 1;
ll marc[KMAX];
pll best[KMAX];
pll best2[KMAX];

vpll children[NMAX];

vpll paths;

void DFS(ll u, ll p, ll d)
{

	level[u] = level[p] + 1;
	
	anc[u][0] = p;
	dist[u][0] = d;
	
	for(ll i = 1;i <= LOGMAX;i++) 
	{
		
		anc[u][i] = anc[ anc[u][i - 1] ][i - 1];
		dist[u][i] = dist[u][i - 1] + dist[ anc[u][i - 1] ][i - 1];
	
	}
	
	for(auto viz : grafo[u])
	{
	
		ll w = viz.fi;
		ll v = viz.se;
	
		if(v == p) continue;
		
		DFS(v, u, w);
	
	}
	
	return;

}

pll Dist(ll u, ll v)
{
	
	ll i, d = 0LL, qtd = 0LL;

	if(level[u] < level[v]) swap(u, v);
	
	for(i = LOGMAX;i >= 0;i--)
	{
		
		if(level[u] - (1 << i) >= level[v]) 
		{
		
			qtd += (1 << i);
			d += dist[u][i];
			u = anc[u][i];
			
		}
	
	}
	
	if(u == v) return {d, qtd};
	
	for(i = LOGMAX;i >= 0;i--)
	{
		
		if(anc[u][i] != anc[v][i]) 
		{
		
			qtd += (1 << i);
			d += dist[u][i];
			qtd += (1 << i);
			d += dist[v][i];
			u = anc[u][i];
			v = anc[v][i];
			
		}
	
	}
	
	i = 0;
	qtd += (1 << i);
	d += dist[u][i];
	qtd += (1 << i);
	d += dist[v][i];

	return {d, qtd};

}

ll DFSCentroid(ll u, ll p)
{

	sub[u] = 1;

	for(auto viz : grafo[u])
	{
	
		ll v = viz.se;
	
		if(v == p || pai[v] != 0) continue;
		
		sub[u] += DFSCentroid(v, u);
		
	}
	
	return sub[u];

}

ll FindCentroid(ll u, ll p)
{

	for(auto viz : grafo[u])
	{
	
		ll v = viz.se;
	
		if(v == p || pai[v] != 0) continue;
		
		if(2 * sub[v] > qtdCent) return FindCentroid(v, u);
	
	}
	
	return u;

}

void BuildCentroid(ll u, ll p)
{

	qtdCent = DFSCentroid(u, u);
	ll centroid = FindCentroid(u, u);

	pai[centroid] = p;

	ordem.push(centroid);

	for(auto viz : grafo[centroid])
	{
	
		ll v = viz.se;
	
		if(pai[v] == 0) BuildCentroid(v, centroid);
	
	}
	
	return;

}

ll Query(pll path, ll who)
{

	ll d = path.fi;
	ll q = path.se;

	if(0 <= m - d && marc[m - d] == caso)
	{
	 
		if(who != best[m - d].se)	return best[m - d].fi + q;
		else						return best2[m - d].fi + q;
		
	}
		
	return NMAX;

}

int best_path (int auxN, int auxM, int h[][2], int l[])
{
	
	ll tam, u, v, w, d, q, pos, resp, i, j, k;
	
	n = auxN;
	m = auxM;
	
	pll path;
	
	resp = NMAX;
	
	for(i = 0;i < n - 1;i++)
	{
	
		u = h[i][0];
		v = h[i][1];
		w = l[i];
		
		u++;
		v++;
		
		grafo[u].pb({w, v});
		grafo[v].pb({w, u});
	
	}
	
	DFS(1, 1, 0);
	BuildCentroid(1, -1);
	
	for(i = 1;i <= n;i++) children[i].pb({i, i});
	
	while(ordem.empty() == false)
	{
	
		u = ordem.top();
		ordem.pop();
		
		tam = children[u].size();
		
		paths.clear();
		for(auto ch : children[u]) paths.pb(Dist(u, ch.fi));
		
		for(i = 0;i < tam;i++)
		{
		
			d = paths[i].fi;
			q = paths[i].se;
			
			if(m < d) continue;

			marc[d] = caso;
			best[d] = {NMAX, -1};
			best2[d] = {NMAX, -1};
					
		}
		
		for(i = 0;i < tam;i++)
		{
		
			d = paths[i].fi;
			q = paths[i].se;
			
			if(m < d) continue;
			
			best[d] = min(best[d], {q, children[u][i].se});
		
		}
		
		for(i = 0;i < tam;i++)
		{
		
			d = paths[i].fi;
			q = paths[i].se;
			
			if(m < d || children[u][i].se == best[d].se) continue;
			
			best2[d] = min(best2[d], {q, children[u][i].se});
		
		}
		
		pos = 0;
		i = 0;
		
		while(i < tam)
		{
		
		
			j = i;
		
			while(j < tam && children[u][i].se == children[u][j].se)
				j++;
				
			v = children[u][i].se;
			
			for(k = i;k < j;k++) 
				resp = min(resp, Query(paths[k], v));
			
			i = j;
		
		}	
		
		v = pai[u];
		
		if(v != -1)
		{
		
			for(auto ch : children[u]) children[v].pb({ch.fi, u});
		
		}
		
		children[u].clear();
		
		caso++;
	
	}
	
	if(resp == NMAX) resp = -1;
	
    return resp;
 
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:205:25: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
  205 |  ll tam, u, v, w, d, q, pos, resp, i, j, k;
      |                         ^~~

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