Submission #1112389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1112389	2024-11-14T07:05:53 Z	VVUU	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N, K, total=1e14;
vector<pair<int, int> > edge[1000010];
int h[1000010];
int siz[1000010];
int wei[1000010];
map<int, int> sav;
void PDF(int n, int cha){
	siz[n]=1;
	for(auto gg:edge[n]){
		int v=gg.first;
		int w=gg.second;
		if(v==cha) continue;
		h[v]=h[n]+1;
		wei[v]=wei[n]+w;
		PDF(v, n);
		siz[n]+=siz[v];
	}
}
void get(int n, int cha, int st){
	if(wei[n]-2*wei[st]<=K){
		int req=K-(wei[n]-2*wei[st]); 
		if(sav[req]==0) sav[req]=1e14;
		total=min(total, h[n]-h[st]+sav[req]-h[st]);
	}
	for(auto v:edge[n]){
		if(v.first==cha) continue;
		get(v.first, n, st);
	}
}
void add(int n, int cha, int val, int st){
	if(sav[wei[n]]==0) sav[wei[n]]=1e14;
	sav[wei[n]]=min(sav[wei[n]], h[n]);
	for(auto gg:edge[n]){
		int v=gg.first;
		if(v==cha) continue;
		add(v, n, val, st);
	}
}
void DFS(int n, int cha, bool keep){
	int found=0;
	for(auto gg:edge[n]){
		int v=gg.first;
		if(v==cha) continue;
		if(found==0 || siz[v]>siz[found]) found=v;
	}
	for(auto gg:edge[n]){
		int v=gg.first;
		if(v==cha || v==found) continue;
		DFS(v, n, 0);
	}
	if(found!=0) DFS(found, n, 1);
	if(sav[wei[n]]==0) sav[wei[n]]=1e14;
	sav[wei[n]]=min(sav[wei[n]], h[n]);
	if(sav[wei[n]+K]==0) sav[wei[n]+K]=1e14;
	total=min(total, sav[wei[n]+K]-h[n]);
	for(auto gg:edge[n]){
		int v=gg.first;
		if(v==cha || v==found) continue;
		get(v, n, n);
		add(v, n, 1, n);
	}
	if(keep==0) add(n, cha, -1, n);
}
signed main(){
//	freopen("goat.inp", "r", stdin);
//	freopen("goat.out", "w", stdout);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>N>>K; h[1]=1; wei[1]=1;
	for(int i=1; i<N; i++){
		int x, y, w; cin>>x>>y>>w; x++; y++;
		edge[x].push_back(make_pair(y, w));
		edge[y].push_back(make_pair(x, w));
	}
	PDF(1, 1);
	DFS(1, 1, 0);
	if(total>=2e11){
		cout<<"-1"; return 0;
	}
	cout<<total;
}

Compilation message

/usr/bin/ld: /tmp/ccrsHcME.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVumyVC.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVumyVC.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status