oj.uz

Submission #110305

# Submission time Handle Problem Language Result Execution time Memory
110305 2019-05-10T15:35:38 Z DystoriaX Race (IOI11_race) C++14
9 / 100
 2118 ms 68116 KB 
#include "race.h"

#include <bits/stdc++.h>

using namespace std;

int n, nn, k;
bitset<200010> al;
vector<pair<int, int> > adj[200010];
vector<int> ch[200010];
int p[200010], sz[200010], d[200010];
long long cost[200010];
set<pair<int, int> > s[200010];
const int lgmx = 18;
int sp[18][200010];

const int INF = 1e9;
int ans = INF;

void dfs(int u, int pp = -1){
	sp[0][u] = pp;
	for(int i = 1; i < lgmx; i++)
		if(sp[i - 1][u] != -1) sp[i][u] = sp[i - 1][sp[i - 1][u]];

	for(auto k : adj[u]){
		int v, w; tie(v, w) = k;

		if(v == pp) continue;

		d[v] = d[u] + 1;
		cost[v] = cost[u] + w;
		dfs(v, u);
	}
}

int lca(int u, int v){
	if(d[u] < d[v]) swap(u, v);

	bitset<lgmx> diff = d[u] - d[v];

	for(int i = lgmx - 1; i >= 0; i--)
		if(diff[i]) u = sp[i][u];

	if(u == v) return v;

	for(int i = lgmx - 1; i >= 0; i--){
		if(sp[i][u] != sp[i][v]){
			u = sp[i][u], v = sp[i][v];
		}
	}

	return sp[0][v];
}

pair<long long, int> getDist(int u, int v){
	int a = lca(u, v);
	return {cost[u] + cost[v] - (cost[a] << 1), d[u] + d[v] - (d[a] << 1)};
}

void findSz(int u, int pp = -1){
	sz[u] = 1;
	nn++;

	for(auto k : adj[u]){
		int v = k.first;
		if(al[v] || v == pp) continue;

		findSz(v, u);
		sz[u] += sz[v];
	}
}

int findCentroid(int u, int pp = -1){
	for(auto k : adj[u]){
		int v = k.first;
		if(al[v] || v == pp || sz[v] <= nn) continue;

		return findCentroid(v, u);
	}

	return u;
}

void decompose(int u, int pp = -1){
	nn = 0;
	findSz(u);

	nn >>= 1;
	int x = findCentroid(u);

	p[x] = pp;
	al[x] = 1;

	for(auto k : adj[x]){
		int v = k.first;
		if(!al[v]) decompose(v, x);
	}
}

void update(int u){
	int x = u;

	while(p[x] != -1){
		long long tp; int len;
		tie(tp, len) = getDist(u, p[x]);
		// cerr << u << " " << x << " " << p[x] << " " << tp << " " << len << endl;

		s[x].insert({tp, len});

		x = p[x];
	}
}

void query(int u){
	int x = u;

	for(auto v : ch[u]){
		auto it = s[v].lower_bound({k, -1});
		if(it -> first == k) ans = min(ans, it -> second);
	}

	while(p[x] != -1){
		long long tp; int len;
		tie(tp, len) = getDist(u, p[x]);
		
		// cerr << "Q: " <<  u << " " << x << " " << p[x] << " " << tp << " " << len << endl;
		
		if(tp > k) return;

		for(auto v : ch[p[x]]){
			if(v == x) continue;

			auto it = s[v].lower_bound({k - tp, -1});

			// cerr << v << " " << (it -> first) << " " << (it -> second) << endl;
			if(it -> first == k - tp) ans = min(ans, len + it -> second);
		}

		x = p[x];
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N, k = K;

	for(int i = 0; i < n - 1; i++){
		adj[H[i][0]].emplace_back(H[i][1], L[i]);
		adj[H[i][1]].emplace_back(H[i][0], L[i]);
	}

	memset(sp, -1, sizeof(sp));
	dfs(0);

	decompose(0);
	
	for(int i = 0; i < n; i++){
		if(p[i] != -1) ch[p[i]].emplace_back(i);

		//cerr << i << " <- " << p[i] << endl;
	}

	for(int i = 0; i < n; i++) update(i);

	for(int i = 0; i < n; i++) query(i);

	if(ans == INF) ans = -1;

	return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33272 KB Output is correct
2 Correct 32 ms 33272 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 32 ms 33272 KB Output is correct
6 Correct 29 ms 33280 KB Output is correct
7 Correct 34 ms 33256 KB Output is correct
8 Correct 28 ms 33272 KB Output is correct
9 Correct 27 ms 33272 KB Output is correct
10 Correct 33 ms 33304 KB Output is correct
11 Correct 28 ms 33280 KB Output is correct
12 Correct 31 ms 33272 KB Output is correct
13 Correct 31 ms 33272 KB Output is correct
14 Correct 31 ms 33408 KB Output is correct
15 Correct 33 ms 33280 KB Output is correct
16 Correct 29 ms 33248 KB Output is correct
17 Correct 35 ms 33280 KB Output is correct
18 Correct 31 ms 33280 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33272 KB Output is correct
2 Correct 32 ms 33272 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 32 ms 33272 KB Output is correct
6 Correct 29 ms 33280 KB Output is correct
7 Correct 34 ms 33256 KB Output is correct
8 Correct 28 ms 33272 KB Output is correct
9 Correct 27 ms 33272 KB Output is correct
10 Correct 33 ms 33304 KB Output is correct
11 Correct 28 ms 33280 KB Output is correct
12 Correct 31 ms 33272 KB Output is correct
13 Correct 31 ms 33272 KB Output is correct
14 Correct 31 ms 33408 KB Output is correct
15 Correct 33 ms 33280 KB Output is correct
16 Correct 29 ms 33248 KB Output is correct
17 Correct 35 ms 33280 KB Output is correct
18 Correct 31 ms 33280 KB Output is correct
19 Correct 31 ms 33320 KB Output is correct
20 Incorrect 27 ms 33280 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33272 KB Output is correct
2 Correct 32 ms 33272 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 32 ms 33272 KB Output is correct
6 Correct 29 ms 33280 KB Output is correct
7 Correct 34 ms 33256 KB Output is correct
8 Correct 28 ms 33272 KB Output is correct
9 Correct 27 ms 33272 KB Output is correct
10 Correct 33 ms 33304 KB Output is correct
11 Correct 28 ms 33280 KB Output is correct
12 Correct 31 ms 33272 KB Output is correct
13 Correct 31 ms 33272 KB Output is correct
14 Correct 31 ms 33408 KB Output is correct
15 Correct 33 ms 33280 KB Output is correct
16 Correct 29 ms 33248 KB Output is correct
17 Correct 35 ms 33280 KB Output is correct
18 Correct 31 ms 33280 KB Output is correct
19 Incorrect 2118 ms 68116 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33272 KB Output is correct
2 Correct 32 ms 33272 KB Output is correct
3 Correct 31 ms 33272 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 32 ms 33272 KB Output is correct
6 Correct 29 ms 33280 KB Output is correct
7 Correct 34 ms 33256 KB Output is correct
8 Correct 28 ms 33272 KB Output is correct
9 Correct 27 ms 33272 KB Output is correct
10 Correct 33 ms 33304 KB Output is correct
11 Correct 28 ms 33280 KB Output is correct
12 Correct 31 ms 33272 KB Output is correct
13 Correct 31 ms 33272 KB Output is correct
14 Correct 31 ms 33408 KB Output is correct
15 Correct 33 ms 33280 KB Output is correct
16 Correct 29 ms 33248 KB Output is correct
17 Correct 35 ms 33280 KB Output is correct
18 Correct 31 ms 33280 KB Output is correct
19 Correct 31 ms 33320 KB Output is correct
20 Incorrect 27 ms 33280 KB Output isn't correct
21 Halted 0 ms 0 KB -