Submission #480133

#	Time	Username	Problem	Language	Result	Execution time	Memory
480133		HamletPetrosyan	Race (IOI11_race)	C++17	100 / 100	1251 ms	36576 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 || nans < ans){
		ans = nans;
	}
}

void sizes(int v, int p){
	sz[v] = 1;
	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];
	}
}

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;
		solve(to, v, d + 1, l + len);

		if(p == -1){
			for(int j = 0; j < len(mas); j++){
				int L = mas[j].second;
				int D = mas[j].first;
				if(L > k) continue;
				if(L == k) {
					update(D);
				} 
				else if (mp.find(k - L) != mp.end()){
					update(mp[k - L] + D);
				}
			}

			for(int j = 0; j < len(mas); j++){
				int dep = mas[j].first, dis = mas[j].second;
				if(dis > k) continue;
				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);

		mp.clear();
		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 - 1; 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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57