oj.uz

Submission #103011

# Submission time Handle Problem Language Result Execution time Memory
103011 2019-03-28T15:33:31 Z hugo_pm Race (IOI11_race) C++17
21 / 100
 3000 ms 87896 KB 
#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 = 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;
}
 
// 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);
	set<pii> tc;
	tc.insert({0,0});
	for (int enf : cen[nod]) {
		proc(enf);
		for (int x : enfants[enf]) {
			enfants[nod].push_back(x);
			int ss = sumEdges(nod, x);
			int ne = nbEdges(nod, x);
			int req = somVoulue - ss;
			auto it2 = tc.lower_bound({req, -1});
			if (it2 != tc.end() && it2->fi == req) {
				chmin(rep, ne + it2->se);
			}
		}
		for (int x : enfants[enf]) {
			tc.insert({sumEdges(nod, x), nbEdges(nod, x)});
		}
	}
}
 
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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14592 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 17 ms 14592 KB Output is correct
5 Correct 16 ms 14564 KB Output is correct
6 Correct 18 ms 14592 KB Output is correct
7 Correct 17 ms 14592 KB Output is correct
8 Correct 17 ms 14592 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Correct 17 ms 14592 KB Output is correct
11 Correct 16 ms 14592 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 11 ms 14620 KB Output is correct
14 Correct 18 ms 14588 KB Output is correct
15 Correct 17 ms 14592 KB Output is correct
16 Correct 19 ms 14508 KB Output is correct
17 Correct 17 ms 14592 KB Output is correct
18 Correct 17 ms 14592 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14592 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 17 ms 14592 KB Output is correct
5 Correct 16 ms 14564 KB Output is correct
6 Correct 18 ms 14592 KB Output is correct
7 Correct 17 ms 14592 KB Output is correct
8 Correct 17 ms 14592 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Correct 17 ms 14592 KB Output is correct
11 Correct 16 ms 14592 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 11 ms 14620 KB Output is correct
14 Correct 18 ms 14588 KB Output is correct
15 Correct 17 ms 14592 KB Output is correct
16 Correct 19 ms 14508 KB Output is correct
17 Correct 17 ms 14592 KB Output is correct
18 Correct 17 ms 14592 KB Output is correct
19 Correct 17 ms 14564 KB Output is correct
20 Correct 16 ms 14592 KB Output is correct
21 Correct 18 ms 14848 KB Output is correct
22 Correct 20 ms 14848 KB Output is correct
23 Correct 21 ms 14848 KB Output is correct
24 Correct 20 ms 14848 KB Output is correct
25 Correct 19 ms 14720 KB Output is correct
26 Correct 20 ms 14848 KB Output is correct
27 Correct 20 ms 14848 KB Output is correct
28 Correct 19 ms 14848 KB Output is correct
29 Correct 18 ms 14848 KB Output is correct
30 Correct 18 ms 14720 KB Output is correct
31 Correct 20 ms 14720 KB Output is correct
32 Correct 19 ms 14720 KB Output is correct
33 Correct 25 ms 14720 KB Output is correct
34 Correct 19 ms 14848 KB Output is correct
35 Correct 19 ms 14848 KB Output is correct
36 Correct 22 ms 14848 KB Output is correct
37 Correct 20 ms 14720 KB Output is correct
38 Correct 21 ms 14848 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14592 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 17 ms 14592 KB Output is correct
5 Correct 16 ms 14564 KB Output is correct
6 Correct 18 ms 14592 KB Output is correct
7 Correct 17 ms 14592 KB Output is correct
8 Correct 17 ms 14592 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Correct 17 ms 14592 KB Output is correct
11 Correct 16 ms 14592 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 11 ms 14620 KB Output is correct
14 Correct 18 ms 14588 KB Output is correct
15 Correct 17 ms 14592 KB Output is correct
16 Correct 19 ms 14508 KB Output is correct
17 Correct 17 ms 14592 KB Output is correct
18 Correct 17 ms 14592 KB Output is correct
19 Correct 833 ms 38576 KB Output is correct
20 Correct 841 ms 38300 KB Output is correct
21 Correct 866 ms 38296 KB Output is correct
22 Correct 682 ms 37360 KB Output is correct
23 Correct 1010 ms 39584 KB Output is correct
24 Correct 469 ms 35356 KB Output is correct
25 Correct 1566 ms 47392 KB Output is correct
26 Correct 939 ms 51060 KB Output is correct
27 Correct 957 ms 62152 KB Output is correct
28 Execution timed out 3036 ms 87896 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14592 KB Output is correct
2 Correct 16 ms 14592 KB Output is correct
3 Correct 16 ms 14592 KB Output is correct
4 Correct 17 ms 14592 KB Output is correct
5 Correct 16 ms 14564 KB Output is correct
6 Correct 18 ms 14592 KB Output is correct
7 Correct 17 ms 14592 KB Output is correct
8 Correct 17 ms 14592 KB Output is correct
9 Correct 15 ms 14592 KB Output is correct
10 Correct 17 ms 14592 KB Output is correct
11 Correct 16 ms 14592 KB Output is correct
12 Correct 15 ms 14592 KB Output is correct
13 Correct 11 ms 14620 KB Output is correct
14 Correct 18 ms 14588 KB Output is correct
15 Correct 17 ms 14592 KB Output is correct
16 Correct 19 ms 14508 KB Output is correct
17 Correct 17 ms 14592 KB Output is correct
18 Correct 17 ms 14592 KB Output is correct
19 Correct 17 ms 14564 KB Output is correct
20 Correct 16 ms 14592 KB Output is correct
21 Correct 18 ms 14848 KB Output is correct
22 Correct 20 ms 14848 KB Output is correct
23 Correct 21 ms 14848 KB Output is correct
24 Correct 20 ms 14848 KB Output is correct
25 Correct 19 ms 14720 KB Output is correct
26 Correct 20 ms 14848 KB Output is correct
27 Correct 20 ms 14848 KB Output is correct
28 Correct 19 ms 14848 KB Output is correct
29 Correct 18 ms 14848 KB Output is correct
30 Correct 18 ms 14720 KB Output is correct
31 Correct 20 ms 14720 KB Output is correct
32 Correct 19 ms 14720 KB Output is correct
33 Correct 25 ms 14720 KB Output is correct
34 Correct 19 ms 14848 KB Output is correct
35 Correct 19 ms 14848 KB Output is correct
36 Correct 22 ms 14848 KB Output is correct
37 Correct 20 ms 14720 KB Output is correct
38 Correct 21 ms 14848 KB Output is correct
39 Correct 833 ms 38576 KB Output is correct
40 Correct 841 ms 38300 KB Output is correct
41 Correct 866 ms 38296 KB Output is correct
42 Correct 682 ms 37360 KB Output is correct
43 Correct 1010 ms 39584 KB Output is correct
44 Correct 469 ms 35356 KB Output is correct
45 Correct 1566 ms 47392 KB Output is correct
46 Correct 939 ms 51060 KB Output is correct
47 Correct 957 ms 62152 KB Output is correct
48 Execution timed out 3036 ms 87896 KB Time limit exceeded
49 Halted 0 ms 0 KB -