oj.uz

Submission #110494

# Submission time Handle Problem Language Result Execution time Memory
110494 2019-05-11T03:24:12 Z DystoriaX Race (IOI11_race) C++14
9 / 100
 2448 ms 75380 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<long long, 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;

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

			auto it = s[v].lower_bound({(long long) 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 31 ms 33408 KB Output is correct
2 Correct 29 ms 33328 KB Output is correct
3 Correct 34 ms 33280 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33280 KB Output is correct
6 Correct 30 ms 33280 KB Output is correct
7 Correct 31 ms 33272 KB Output is correct
8 Correct 32 ms 33272 KB Output is correct
9 Correct 32 ms 33272 KB Output is correct
10 Correct 33 ms 33252 KB Output is correct
11 Correct 32 ms 33272 KB Output is correct
12 Correct 36 ms 33252 KB Output is correct
13 Correct 35 ms 33380 KB Output is correct
14 Correct 31 ms 33272 KB Output is correct
15 Correct 31 ms 33272 KB Output is correct
16 Correct 39 ms 33272 KB Output is correct
17 Correct 31 ms 33400 KB Output is correct
18 Correct 31 ms 33348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33408 KB Output is correct
2 Correct 29 ms 33328 KB Output is correct
3 Correct 34 ms 33280 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33280 KB Output is correct
6 Correct 30 ms 33280 KB Output is correct
7 Correct 31 ms 33272 KB Output is correct
8 Correct 32 ms 33272 KB Output is correct
9 Correct 32 ms 33272 KB Output is correct
10 Correct 33 ms 33252 KB Output is correct
11 Correct 32 ms 33272 KB Output is correct
12 Correct 36 ms 33252 KB Output is correct
13 Correct 35 ms 33380 KB Output is correct
14 Correct 31 ms 33272 KB Output is correct
15 Correct 31 ms 33272 KB Output is correct
16 Correct 39 ms 33272 KB Output is correct
17 Correct 31 ms 33400 KB Output is correct
18 Correct 31 ms 33348 KB Output is correct
19 Correct 30 ms 33272 KB Output is correct
20 Incorrect 31 ms 33236 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33408 KB Output is correct
2 Correct 29 ms 33328 KB Output is correct
3 Correct 34 ms 33280 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33280 KB Output is correct
6 Correct 30 ms 33280 KB Output is correct
7 Correct 31 ms 33272 KB Output is correct
8 Correct 32 ms 33272 KB Output is correct
9 Correct 32 ms 33272 KB Output is correct
10 Correct 33 ms 33252 KB Output is correct
11 Correct 32 ms 33272 KB Output is correct
12 Correct 36 ms 33252 KB Output is correct
13 Correct 35 ms 33380 KB Output is correct
14 Correct 31 ms 33272 KB Output is correct
15 Correct 31 ms 33272 KB Output is correct
16 Correct 39 ms 33272 KB Output is correct
17 Correct 31 ms 33400 KB Output is correct
18 Correct 31 ms 33348 KB Output is correct
19 Incorrect 2448 ms 75380 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33408 KB Output is correct
2 Correct 29 ms 33328 KB Output is correct
3 Correct 34 ms 33280 KB Output is correct
4 Correct 30 ms 33280 KB Output is correct
5 Correct 29 ms 33280 KB Output is correct
6 Correct 30 ms 33280 KB Output is correct
7 Correct 31 ms 33272 KB Output is correct
8 Correct 32 ms 33272 KB Output is correct
9 Correct 32 ms 33272 KB Output is correct
10 Correct 33 ms 33252 KB Output is correct
11 Correct 32 ms 33272 KB Output is correct
12 Correct 36 ms 33252 KB Output is correct
13 Correct 35 ms 33380 KB Output is correct
14 Correct 31 ms 33272 KB Output is correct
15 Correct 31 ms 33272 KB Output is correct
16 Correct 39 ms 33272 KB Output is correct
17 Correct 31 ms 33400 KB Output is correct
18 Correct 31 ms 33348 KB Output is correct
19 Correct 30 ms 33272 KB Output is correct
20 Incorrect 31 ms 33236 KB Output isn't correct
21 Halted 0 ms 0 KB -