Submission #110300

#	Time	Username	Problem	Language	Result	Execution time	Memory
110300		DystoriaX	Race (IOI11_race)	C++14	0 / 100	46 ms	33400 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<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];
}

long long getDist(int u, int v){
	return cost[u] + cost[v] - (cost[lca(u, v)] << 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;

	int len = 1;
	while(p[x] != -1){
		long long tp = getDist(u, p[x]);
		// cerr << u << " " << x << " " << p[x] << " " << tp << " " << len + 1 << 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);
	}

	int len = 1;
	while(p[x] != -1){
		long long tp = getDist(u, p[x]);
		
		if(tp > k) return;

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

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

			if(it -> first == k - tp) ans = min(ans, len + it -> second);
		}

		x = p[x];
		++len;
	}
}

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