oj.uz

Submission #915201

# Submission time Handle Problem Language Result Execution time Memory
915201 2024-01-23T13:23:28 Z guilhermecpp Race (IOI11_race) C++17
100 / 100
 1066 ms 214004 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27480 KB Output is correct
2 Correct 8 ms 27484 KB Output is correct
3 Correct 7 ms 27480 KB Output is correct
4 Correct 6 ms 27316 KB Output is correct
5 Correct 6 ms 27484 KB Output is correct
6 Correct 7 ms 27452 KB Output is correct
7 Correct 9 ms 27484 KB Output is correct
8 Correct 7 ms 27480 KB Output is correct
9 Correct 7 ms 27480 KB Output is correct
10 Correct 6 ms 27484 KB Output is correct
11 Correct 7 ms 27480 KB Output is correct
12 Correct 7 ms 27484 KB Output is correct
13 Correct 13 ms 27640 KB Output is correct
14 Correct 6 ms 27484 KB Output is correct
15 Correct 7 ms 27460 KB Output is correct
16 Correct 6 ms 27484 KB Output is correct
17 Correct 6 ms 27484 KB Output is correct
18 Correct 6 ms 27484 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27480 KB Output is correct
2 Correct 8 ms 27484 KB Output is correct
3 Correct 7 ms 27480 KB Output is correct
4 Correct 6 ms 27316 KB Output is correct
5 Correct 6 ms 27484 KB Output is correct
6 Correct 7 ms 27452 KB Output is correct
7 Correct 9 ms 27484 KB Output is correct
8 Correct 7 ms 27480 KB Output is correct
9 Correct 7 ms 27480 KB Output is correct
10 Correct 6 ms 27484 KB Output is correct
11 Correct 7 ms 27480 KB Output is correct
12 Correct 7 ms 27484 KB Output is correct
13 Correct 13 ms 27640 KB Output is correct
14 Correct 6 ms 27484 KB Output is correct
15 Correct 7 ms 27460 KB Output is correct
16 Correct 6 ms 27484 KB Output is correct
17 Correct 6 ms 27484 KB Output is correct
18 Correct 6 ms 27484 KB Output is correct
19 Correct 6 ms 27484 KB Output is correct
20 Correct 8 ms 27480 KB Output is correct
21 Correct 7 ms 27484 KB Output is correct
22 Correct 13 ms 58460 KB Output is correct
23 Correct 11 ms 53596 KB Output is correct
24 Correct 13 ms 58412 KB Output is correct
25 Correct 11 ms 46172 KB Output is correct
26 Correct 9 ms 39000 KB Output is correct
27 Correct 7 ms 27740 KB Output is correct
28 Correct 8 ms 33884 KB Output is correct
29 Correct 9 ms 39004 KB Output is correct
30 Correct 9 ms 39260 KB Output is correct
31 Correct 10 ms 48220 KB Output is correct
32 Correct 11 ms 46168 KB Output is correct
33 Correct 12 ms 55644 KB Output is correct
34 Correct 11 ms 48996 KB Output is correct
35 Correct 12 ms 56156 KB Output is correct
36 Correct 12 ms 58460 KB Output is correct
37 Correct 12 ms 48576 KB Output is correct
38 Correct 10 ms 38748 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27480 KB Output is correct
2 Correct 8 ms 27484 KB Output is correct
3 Correct 7 ms 27480 KB Output is correct
4 Correct 6 ms 27316 KB Output is correct
5 Correct 6 ms 27484 KB Output is correct
6 Correct 7 ms 27452 KB Output is correct
7 Correct 9 ms 27484 KB Output is correct
8 Correct 7 ms 27480 KB Output is correct
9 Correct 7 ms 27480 KB Output is correct
10 Correct 6 ms 27484 KB Output is correct
11 Correct 7 ms 27480 KB Output is correct
12 Correct 7 ms 27484 KB Output is correct
13 Correct 13 ms 27640 KB Output is correct
14 Correct 6 ms 27484 KB Output is correct
15 Correct 7 ms 27460 KB Output is correct
16 Correct 6 ms 27484 KB Output is correct
17 Correct 6 ms 27484 KB Output is correct
18 Correct 6 ms 27484 KB Output is correct
19 Correct 307 ms 90192 KB Output is correct
20 Correct 292 ms 89800 KB Output is correct
21 Correct 275 ms 89568 KB Output is correct
22 Correct 256 ms 86560 KB Output is correct
23 Correct 262 ms 94772 KB Output is correct
24 Correct 183 ms 80824 KB Output is correct
25 Correct 374 ms 103132 KB Output is correct
26 Correct 234 ms 106036 KB Output is correct
27 Correct 338 ms 131764 KB Output is correct
28 Correct 859 ms 182856 KB Output is correct
29 Correct 917 ms 181664 KB Output is correct
30 Correct 362 ms 133240 KB Output is correct
31 Correct 341 ms 131812 KB Output is correct
32 Correct 496 ms 134268 KB Output is correct
33 Correct 742 ms 159456 KB Output is correct
34 Correct 745 ms 158872 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27480 KB Output is correct
2 Correct 8 ms 27484 KB Output is correct
3 Correct 7 ms 27480 KB Output is correct
4 Correct 6 ms 27316 KB Output is correct
5 Correct 6 ms 27484 KB Output is correct
6 Correct 7 ms 27452 KB Output is correct
7 Correct 9 ms 27484 KB Output is correct
8 Correct 7 ms 27480 KB Output is correct
9 Correct 7 ms 27480 KB Output is correct
10 Correct 6 ms 27484 KB Output is correct
11 Correct 7 ms 27480 KB Output is correct
12 Correct 7 ms 27484 KB Output is correct
13 Correct 13 ms 27640 KB Output is correct
14 Correct 6 ms 27484 KB Output is correct
15 Correct 7 ms 27460 KB Output is correct
16 Correct 6 ms 27484 KB Output is correct
17 Correct 6 ms 27484 KB Output is correct
18 Correct 6 ms 27484 KB Output is correct
19 Correct 6 ms 27484 KB Output is correct
20 Correct 8 ms 27480 KB Output is correct
21 Correct 7 ms 27484 KB Output is correct
22 Correct 13 ms 58460 KB Output is correct
23 Correct 11 ms 53596 KB Output is correct
24 Correct 13 ms 58412 KB Output is correct
25 Correct 11 ms 46172 KB Output is correct
26 Correct 9 ms 39000 KB Output is correct
27 Correct 7 ms 27740 KB Output is correct
28 Correct 8 ms 33884 KB Output is correct
29 Correct 9 ms 39004 KB Output is correct
30 Correct 9 ms 39260 KB Output is correct
31 Correct 10 ms 48220 KB Output is correct
32 Correct 11 ms 46168 KB Output is correct
33 Correct 12 ms 55644 KB Output is correct
34 Correct 11 ms 48996 KB Output is correct
35 Correct 12 ms 56156 KB Output is correct
36 Correct 12 ms 58460 KB Output is correct
37 Correct 12 ms 48576 KB Output is correct
38 Correct 10 ms 38748 KB Output is correct
39 Correct 307 ms 90192 KB Output is correct
40 Correct 292 ms 89800 KB Output is correct
41 Correct 275 ms 89568 KB Output is correct
42 Correct 256 ms 86560 KB Output is correct
43 Correct 262 ms 94772 KB Output is correct
44 Correct 183 ms 80824 KB Output is correct
45 Correct 374 ms 103132 KB Output is correct
46 Correct 234 ms 106036 KB Output is correct
47 Correct 338 ms 131764 KB Output is correct
48 Correct 859 ms 182856 KB Output is correct
49 Correct 917 ms 181664 KB Output is correct
50 Correct 362 ms 133240 KB Output is correct
51 Correct 341 ms 131812 KB Output is correct
52 Correct 496 ms 134268 KB Output is correct
53 Correct 742 ms 159456 KB Output is correct
54 Correct 745 ms 158872 KB Output is correct
55 Correct 19 ms 34416 KB Output is correct
56 Correct 20 ms 34520 KB Output is correct
57 Correct 183 ms 94008 KB Output is correct
58 Correct 57 ms 72668 KB Output is correct
59 Correct 237 ms 108084 KB Output is correct
60 Correct 923 ms 203204 KB Output is correct
61 Correct 360 ms 134068 KB Output is correct
62 Correct 338 ms 131260 KB Output is correct
63 Correct 477 ms 132412 KB Output is correct
64 Correct 786 ms 159456 KB Output is correct
65 Correct 647 ms 143956 KB Output is correct
66 Correct 1066 ms 214004 KB Output is correct
67 Correct 301 ms 115508 KB Output is correct
68 Correct 555 ms 154224 KB Output is correct
69 Correct 568 ms 154096 KB Output is correct
70 Correct 536 ms 151668 KB Output is correct