Submission #480124

#	Time	Username	Problem	Language	Result	Execution time	Memory
480124		HamletPetrosyan	Race (IOI11_race)	C++17	0 / 100	4 ms	4940 KiB

race

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

#define len(a) ((int)a.size())

const int N = 200005;

int ans = -1;
vector< pair<int, int> > g[N];
int sz[N], all, k;
bool used[N];

void update(int nans){
	if(ans == -1){
		ans = nans;
		return;
	}
	ans = min(ans, nans);
}

void sizes(int v, int p){
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i].first;
		if(to == p || used[to]) continue;
		sizes(to, v);
		sz[v] += sz[to];
	}
	sz[v]++;
}

int cfind(int v, int p){
	if(p == -1){
		all = sz[v];
	}
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i].first;
		if(to == p || used[to]) continue;
		if(sz[to] > (all / 2)) {
			return cfind(to, v);
		}
	}
	return v;
}

vector< pair<int, int> > mas;
map<int, int> mp;

void solve(int v, int p, int d, int l){
	if(p != -1){
		mas.push_back(make_pair(d, l));
	}
	for(int i = 0; i < len(g[v]); i++){
		int to = g[v][i].first, len = g[v][i].second;
		if(to == p || used[to]) continue;
		if(l > k) break;
		if(l == k) {
			update(d);
		} 
		else if (mp.find(k - l) != mp.end()){
			update(mp[k - l] + d);
		}
		solve(to, v, d + 1, l + len);

		if(p == -1){
			for(int j = 0; j < len(mas); j++){
				int dep = mas[i].first, dis = mas[i].second;
				if(mp.find(dis) != mp.end()){
					mp[dis] = min(mp[dis], dep);
				}
				else {
					mp[dis] = dep;
				}
			}
			mas.clear();
		}
	}
}

void centroid_decomposition(){
	queue<int> q;
	q.push(1);

	while(!q.empty()){
		int v = q.front();
		q.pop();

		sizes(v, -1);
		v = cfind(v, -1);
		sizes(v, -1);

		solve(v, -1, 0, 0);

		used[v] = true;
		for(int i = 0; i < len(g[v]); i++){
			int to = g[v][i].first;
			if(used[to]) continue;
			if(sz[to] == 1) continue;
			q.push(to);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	k = K;
	for(int i = 0; i < N; i++){
		int u = H[i][0], v = H[i][1], d = L[i];
		g[u].push_back(make_pair(v, d));
		g[v].push_back(make_pair(u, d));
	}	

	centroid_decomposition();

	return ans;
}

//int main(){
//	int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
//	int H[][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
//
//	cout << best_path(11, 12, H, L) << endl;
//	return 0;
//}

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