Submission #100836

#	Time	Username	Problem	Language	Result	Execution time	Memory
100836		RafaelSus	Race (IOI11_race)	C++14	100 / 100	636 ms	35264 KiB

race

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int n,k;
bool used_2[200002];
vector<pair<int,int>>g[200002];
int size[200002];
int tree_centroid;
int best[1000002];
const int inf = 1e9;
int ans = 1e9;
 
void dfs(int node, int dad = -1)
{
	size[node] = 1;
	for (auto it : g[node])
		if (!used_2[it.first] && it.first != dad)
		{
			dfs(it.first, node);
			size[node] += size[it.first];
		}
}
 
 
void findcentroid(int v, int p, int flo){
//	used_1[v]=true;
	int zib=0;
	for(auto x:g[v]){
		if(used_2[x.first] || x.first==p)continue;
		if(size[x.first] - 1 >= flo){
			zib++;
			findcentroid(x.first, v, flo);
			break;
		}
	}
	if(zib==0)
		tree_centroid=v;
}
 
void dfs2(int x, int p, int cost, int l, vector<pair<int,int>>&to_ans) {
	if (cost <= k) 
		to_ans.push_back(make_pair(cost, l));
 
	for (auto y : g[x]) {
		if (used_2[y.first] || y.first == p)continue;
		dfs2(y.first, x, cost + y.second, l + 1, to_ans);
	}
}
 
 
int solve(int node) {
	dfs(node);
//	fill(used_1, used_1 + n, false);
	int zibil = size[node] - 1;
	findcentroid(node, -1, zibil / 2);
	node = tree_centroid;
	best[0] = 0;
 
	vector<int>del;
	vector<pair<int, int>>to_ans;
 
	for (auto x : g[node]) {
		int son = x.first;
		if (used_2[son])continue;
		to_ans.clear();
		dfs2(x.first, node, x.second, 1, to_ans);
 
		for (auto it : to_ans)
			ans = min(ans, it.second + best[k - it.first]);
 
 
		for (auto it : to_ans)
		{
			best[it.first] = min(best[it.first], it.second);
			del.push_back(it.first);
		}
	}
	for (auto it : del)
		best[it] = inf;
 
	used_2[node] = true;
 
 
	for (auto it : g[node])
		if (!used_2[it.first])
			ans = min(ans, solve(it.first));
 
	return ans;
}
 
 
int best_path(int N, int _K, int H[][2], int L[])
{
    k = _K;
  	n = N;
    int i;
    for(i=0; i<N-1; ++i)
    {
        int x, y, z;
        x = H[i][0];
        y = H[i][1];
        z = L[i];
 
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
    }
 
    for(i=0; i<=k; ++i) best[i] = inf;
 
    int X = solve(0);
    if(X == inf) return -1;
    return X;
}

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