Submission #865539

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

race

#include<bits/stdc++.h>
#define ll int
#define pp pair<ll,ll>
#define f first
#define s second
using namespace std;
ll N,K,L[200001],i,a,b,ans=200010,sz[200001],H[200001][2];
bitset<200001> mark;
map<ll,ll> mp;
vector<pp> G[200001];
ll getsize(ll a,ll p=-1){
	sz[a]=1;
	for(pp i:G[a]){
		if(p!=i.f && !mark[i.f]) 
			sz[a]+=getsize(i.f,a);
	}
	return sz[a];
}
ll centroid(ll a,ll p,ll n){
	for(pp i:G[a]){
		if(p!=i.f && sz[i.f]>n/2 && !mark[i.f])
			return centroid(i.f,a,n);
	}
	return a;
}
void dfs(ll a,ll p,ll dist,ll len,bool key){
	if(dist>K) return;
	if(dist==K){
		ans=min(ans,len);
		return;
	}
	if(key){
		if(mp[K-dist]) 
			ans=min(ans,len+mp[K-dist]);
	}
	else{
		if(!mp[dist]) mp[dist]=len;
		else mp[dist]=min(mp[dist],len);
	}
	for(pp i:G[a]){
		if(p!=i.f && !mark[i.f]){
			dfs(i.f,a,dist+i.s,len+1,key);
		}	
	}
}
void solve(ll a){
	ll n,cnt;
	n=getsize(a);
	cnt=centroid(a,0,n);
	mark[cnt]=1;
	mp.clear();
	for(pp i:G[cnt]){
		if(!mark[i.f]){
			dfs(i.f,cnt,i.s,1,1);
			dfs(i.f,cnt,i.s,1,0);
		}
	}
	for(pp i:G[cnt]){
		if(!mark[i.f])
			solve(i.f);
	}
}
ll best_path(ll N,ll K,ll H[][2],ll L[]){
	for(i=1;i<N;i++){
		a=H[i][0]+1;
		b=H[i][1]+1;
		G[a].push_back({b,L[i]});
		G[b].push_back({a,L[i]});
	}
	solve(1);
	if(ans==200010) return -1;
	return ans;
}
ll cur;
int main(){
	cin >> N >> K;
	for(i=1;i<N;i++){
		cin >> H[i][0] >> H[i][1] >> L[i];
	}
	cur=best_path(N,K,H,L);
	cout << cur;
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccK7mZJN.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cci9P8JN.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status