Submission #163951

#	Time	Username	Problem	Language	Result	Execution time	Memory
163951		tushar_2658	Race (IOI11_race)	C++14	0 / 100	35 ms	36344 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, 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), make_pair(dis1(cur_c, x), x)));
	}
	for(auto i : edges[x]){
		if(i.first == p)continue;
		dfs1(i.first, x);
	}
}

vector<int> t[maxn];
int st[maxn], ed[maxn];
int cnt = 0, root; 

void centroid_euler(int x, int p){
	st[x] = ++cnt; 
	for(auto i : t[x]){
		if(i == p)continue;
		centroid_euler(i, x);
	}
	ed[x] = cnt;
}

void build(int x, int p){
	dfs(x, 0);
	int c = centroid(x, 0, sub[x] / 2);
	par[c] = p;
	if(p == 0)root = c;
	else {
		t[p].push_back(c);
		t[c].push_back(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);
	}
}

bool inside(int x, int p){
	if(st[x] >= st[p] && ed[x] <= ed[p])return 1;
	return 0;
}

int query(int x){
	int l = k, u = x, prev = -1;
	int ret = INT_MAX;
	while(x != 0){
		int left = l - dis(x, u); 
		if(left < 0){
			x = par[x];
			continue;
		}
		vector<pair<int, pair<int, int>>>:: iterator itr = lower_bound(ms[x].begin(), ms[x].end(), make_pair(left, make_pair(-1, -1)));
		if(itr == ms[x].end()){
			x = par[x];
			continue;
		}
		int idx = itr - ms[x].begin();
		if(prev != -1){
			while(inside(ms[x][idx].second.second, prev) && idx < (int)ms[x].size()){
				idx++;
			}
		}
		if(ms[x][idx].first == left){
			ret = min(ret, ms[x][idx].second.first + dis1(x, u));
		}
		prev = x;
		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);
	centroid_euler(root, root);
	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