Submission #865469

#	Time	Username	Problem	Language	Result	Execution time	Memory
865469		tamir1	Race (IOI11_race)	C++14	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;
	ll i;
	for(i=0;i<G[a].size();i++){
		if(p!=G[a][i].f && !mark[G[a][i].f]) 
			sz[a]+=getsize(G[a][i].f,a);
	}
	return sz[a];
}
ll centroid(ll a,ll p,ll n){
	ll i;
	for(i=0;i<G[a].size();i++){
		if(p!=G[a][i].f && sz[G[a][i].f]>n/2 && !mark[G[a][i].f])
			return centroid(G[a][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);
	}
	ll i;
	for(i=0;i<G[a].size();i++){
		if(p!=G[a][i].f && !mark[G[a][i].f]){
			dfs(G[a][i].f,a,dist+G[a][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();
	ll i;
	for(i=0;i<G[cnt].size();i++){
		if(!mark[G[a][i].f]){
			dfs(G[a][i].f,cnt,G[a][i].s,1,1);
			dfs(G[a][i].f,cnt,G[a][i].s,1,0);
		}
	}
	for(i=0;i<G[cnt].size();i++){
		if(!mark[G[a][i].f])
			solve(G[a][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)

race.cpp: In function 'int getsize(int, int)':
race.cpp:14:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(i=0;i<G[a].size();i++){
      |          ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(i=0;i<G[a].size();i++){
      |          ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, bool)':
race.cpp:43:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(i=0;i<G[a].size();i++){
      |          ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:56:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(i=0;i<G[cnt].size();i++){
      |          ~^~~~~~~~~~~~~~
race.cpp:62:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(i=0;i<G[cnt].size();i++){
      |          ~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccJ9nuAw.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccR84Ryw.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status