Submission #163945

#	Time	Username	Problem	Language	Result	Execution time	Memory
163945		tushar_2658	Race (IOI11_race)	C++14	0 / 100	32 ms	31608 KiB

race

#include "bits/stdc++.h"
using namespace std;

const int maxn = 200005;
int n, k;
set<pair<int, int>> edges[maxn];
int sub[maxn], par[maxn], d[maxn], dp[maxn][22], depth[maxn];

void rem(pair<int, int> x, int y){
	edges[y].erase(x);
	edges[x.first].erase(make_pair(y, x.second));
}

void dfs(int x, int p){
	sub[x] = 1;
	for(auto i : edges[x]){
		if(i.first == p)continue;
		dfs(i.first, x);
		sub[x] += sub[i.first];
	}
}

int centroid(int x, int p, int range){
	for(auto i : edges[x]){
		if(i.first == p)continue;
		if(sub[i.first] > range)return centroid(i.first, x, range);
	}return x;
}

vector<pair<int, int>> ms[maxn];
int cur_c;

void get(int x, int p, int dd){
	dp[x][0] = p;
	depth[x] = depth[p] + 1;
	d[x] = d[p] + dd;
	for(auto i : edges[x]){
		if(i.first == p)continue;
		get(i.first, x, i.second);
	}
}

int lca(int x, int y){
	if(depth[x] < depth[y])swap(x, y);
	for(int i = 21; i >= 0; i--){
		if(depth[x] - (1 << i) >= depth[y]){
			x = dp[x][i];
		}
	}
	if(x == y)return x;
	for(int i = 21; i >= 0; i--){
		if(dp[x][i] != dp[y][i] && dp[x][i] != -1 && dp[y][i] != -1){
			x = dp[x][i];
			y = dp[y][i];
		}
	}
	return dp[x][0];
}

int dis(int x, int y){
	return d[x] + d[y] - 2 * d[lca(x, y)];
}

int dis1(int x, int y){
	return depth[x] + depth[y] - 2 * depth[lca(x, y)];
}

void dfs1(int x, int p){
	if(cur_c != x){
		ms[cur_c].push_back(make_pair(dis(cur_c, x), dis1(cur_c, x)));
	}
	for(auto i : edges[x]){
		if(i.first == p)continue;
		dfs1(i.first, x);
	}
}

void build(int x, int p){
	dfs(x, 0);
	int c = centroid(x, 0, sub[x] / 2);
	par[c] = p;
	cur_c = c;
	dfs1(c, p);
	sort(ms[cur_c].begin(), ms[cur_c].end());
	vector<pair<int, int>> v;
	copy(edges[c].begin(), edges[c].end(), back_inserter(v));
	for(auto i : v){
		rem(i, c);
		build(i.first, c);
	}
}

int query(int x){
	int l = k, u = x;
	int ret = INT_MAX;
	while(x != 0){
		int left = l - dis(x, u);
		if(left < 0){
			x = par[x];
			continue;
		}
		int lo = 0, hi = ms[x].size() - 1, ans = -1;
		while(lo <= hi){
			int mid = (lo + hi) / 2; 
			if(ms[x][mid].first >= left){
				ans = mid;
				hi = mid - 1;
			}else {
				lo = mid + 1;
			}
		}
		if(ans == -1){
			x = par[x];
			continue;
		}
		if(ms[x][ans].first == left){
			ret = min(ret, ms[x][ans].second + dis1(x, u));
		}
		x = par[x];
	}return ret;
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K; 
	for(int i = 0; i < n - 1; i++){
		edges[H[i][0] + 1].insert(make_pair(H[i][1] + 1, L[i]));
		edges[H[i][1] + 1].insert(make_pair(H[i][0] + 1, L[i]));
	}
	memset(dp, -1, sizeof dp);
	get(1, 0, 0);
	for(int j = 1; j < 22; j++){
		for(int i = 1; i <= n; i++){
			if(dp[i][j - 1] != -1){
				dp[i][j] = dp[dp[i][j - 1]][j - 1];
			}
		}
	}
	build(1, 0);
	int ans = INT_MAX;
	for(int i = 1; i <= n; i++){
		ans = min(ans, query(i));
	}
	return (ans >= INT_MAX ? -1 : ans);
}

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