Submission #110494

#	Time	Username	Problem	Language	Result	Execution time	Memory
110494		DystoriaX	Race (IOI11_race)	C++14	9 / 100	2448 ms	75380 KiB

race

#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 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57