Submission #386871

#	Time	Username	Problem	Language	Result	Execution time	Memory
386871		minoum	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e6+10, inf = 1e6+3;
int n, k, mn[MAXN], ans = inf, all, sz[MAXN], par[MAXN], h[MAXN];
vector <pair<int,int>> adj[MAXN];
vector <int> clr;
ll d[MAXN];
bool dead[MAXN];

void dfs(int v, int parv){
 	all++; sz[v] = 1;
	for(auto u: adj[v]){
		if(!dead[u.first] && u.first != parv){
			par[u.first] = v;
			dfs(u.first, v);
			sz[v] += sz[u.first];
		}
	}
	return;
}

inline int findcentroid(int v){
	all = 0;
	int cent = v; par[v] = -1;
	dfs(v, -1);
	bool f = false; 
	while(!f){
		f = true;
		for(auto u: adj[cent]){
			if(!dead[u.first] && u.first != par[cent] && sz[u.first] >= (all / 2)){
				f = false;
				cent = u.first;
				break;
			}
		}
	}
	return cent;
}

void see(int v, int parv){
	if(d[v]<=k) ans = min(ans, h[v]+mn[k-d[v]]);
	for(auto i: adj[v]){
		int u = i.first, w = i.second;
		if(dead[u] || u==parv) continue;
		h[u] = h[v]+1; d[u] = d[v]+(ll)w;
		see(u, v);
	}
	return;
}

void add(int v, int parv){
	if(d[v]<k){
		mn[d[v]] = min(mn[d[v]], h[v]); 
		clr.push_back(d[v]);
	}
	for(auto i: adj[v]){
		int u = i.first;
		if(dead[u] || u == parv) continue;
		add(u,v);
	}
	return;
}

inline void calc(int r){
	mn[0] = 0; h[r] = 0; d[r] = 0; clr.push_back(0);
	for(auto i: adj[r]){
		int u = i.first;
		if(dead[u]) continue;
		h[u] = 1; d[u] = (ll)i.second;
		see(u, r);
		add(u, r);
	}
	while(!clr.empty()){
		mn[clr.back()] = inf; clr.pop_back();
	}
	return;
}

void slv(int v, int tt = 0){
	int cent = findcentroid(v);
	calc(cent);
	dead[cent] = true;
	for(auto u: adj[cent])
		if(!dead[u.first]) slv(u.first, tt+1);
	return;
}

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]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	for(int i = 0; i < MAXN; i++) mn[i] = inf;
	slv(0);
	return (ans>=inf?-1:ans);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n-1; i++){
		int u,v,w;
		cin >> u >> v >> w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i = 0; i < MAXN; i++) mn[i] = inf;
	slv(0);
	cout << (ans>=inf?-1:ans) << endl;
	return 0; 
}

Compilation message (stderr)

/tmp/cctgXCQa.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccDS6uHY.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status