Submission #379103

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

race

#include <bits/stdc++.h>
using namespace std;
 
int n,m,u,z,w,ct[1000005],sum,ans,node,sz[200005];
vector <pair<int,int>  > edge[200005];
vector <pair<int,int>  > v;
bool vis[200005],del[200005],ok,cen[200005];
void dfs(int x){
	vis[x]=true; sz[x]=1;
	for (int i=0;i<(int)edge[x].size();i++){
		if (!vis[edge[x][i].first]){
			dfs(edge[x][i].first);
			sz[x]+=sz[edge[x][i].first];
		}
	}
}
void find_centroid(int x,int nowsz){
	if (node != -1)
	goto byew;
	cen[x]=true;
	for (int i=0;i<(int)edge[x].size();i++){
		if (sz[edge[x][i].first] < sz[x] && sz[edge[x][i].first]*2 > nowsz)
		goto gg;
	} 
	if ((nowsz-sz[x])*2 <= nowsz)
	node=x;
	gg:;
	for (int i=0;i<(int)edge[x].size();i++){
		if (!cen[edge[x][i].first] && !del[edge[x][i].first] && node == -1)
		find_centroid(edge[x][i].first,nowsz);		
	}
	byew:;
}
void ggto(int x,int dis,int num){
	vis[x]=true; ok=false; sz[x]=1;
	for (int i=0;i<(int)edge[x].size();i++){
		if (!vis[edge[x][i].first] && !del[edge[x][i].first]){
			ok=true;
			ggto(edge[x][i].first,dis+edge[x][i].second,num+1);
			sz[x]+=sz[edge[x][i].first];
		}
	}
	if (!ok)
	v.push_back(make_pair(dis,num));
}
void div_and_con(int x,int nowsz){
	for (int i=0;i<n;i++){
		vis[i]=false; 
		cen[i]=false;
	}
	for (int i=1;i<=m;i++){
		ct[i]=1e9;
	} 
	v.clear(); sz[x]=1;
	for (int i=0;i<(int)edge[x].size();i++){
		if (!vis[edge[x][i].first] && !del[edge[x][i].first]){
			v.clear(); 
			ggto(edge[x][i].first,edge[x][i].second,1);
			for (int j=0;j<(int)v.size();j++){
			if (v[j].first <= m)
				ans=min(ans,ct[m-v[j].first]+v[j].second);
			}
			for (int j=0;j<(int)v.size();j++){
				if (v[j].first <= m)
				ct[v[j].first]=min(ct[v[j].first],v[j].second);
			}
			sz[x]+=sz[edge[x][i].first];
		}
	}
	for (int i=0;i<(int)edge[x].size();i++){
		if (!del[edge[x][i].first] && sz[edge[x][i].first] > 1){
			node=-1;
			find_centroid(edge[x][i].first,sz[edge[x][i].first]);
			del[node]=true;
			div_and_con(node,sz[edge[x][i].first]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m; ans=1e9;
	for (int i=1;i<n;i++){
		cin >> u >> z >> w;
		edge[u].push_back(make_pair(z,w));
		edge[z].push_back(make_pair(u,w));
	}
	dfs(0);
	for (int i=0;i<n;i++){
		for (int j=0;j<(int)edge[i].size();j++){
			if (sz[edge[i][j].first] < sz[i] && sz[edge[i][j].first]*2 > n)
			goto out;
		}
		if ((n-sz[i])*2 <= n){
			del[i]=true;
			div_and_con(i,n);
			break;
		}
		out:;
	}
	if (ans == 1e9)
	cout << "-1\n";
	else
	cout << ans << "\n";
	return 0;
}	

Compilation message (stderr)

/tmp/ccKWbteT.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccAC8ykQ.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccAC8ykQ.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status