Submission #116595

#	Time	Username	Problem	Language	Result	Execution time	Memory
116595		khulegub	Race (IOI11_race)	C++14	0 / 100	2 ms	384 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
using namespace std;
typedef pair<int,int> ii;
vector<vector<ii> > to;
int k;
int subsz;
int sz[200020];
bool block[200020];
map<int,int> bag;
map<int,bool> bagex;
map<int,bool> subbagex;
map<int,int> subbag;
int ans=1e9;
void dosz(int u,int pre){
	sz[u]=1;
	for(ii vw : to[u]){
		int v=vw.xx;
		if(v!=pre&&(!block[v])){
			dosz(v,u);
			sz[u]+=sz[v];
		}
	}
}
int findcentr(int u,int pre){
	for(ii vw : to[u]){
		int v=vw.xx;
		if(v!=pre&&(!block[v])){
			if(sz[v]>subsz/2) return findcentr(v,u);
		}
	}
	return u;
}
void putwt(int u,int pre,int w,int l){
	if(subbagex[w]){
		subbag[w]=min(subbag[w],l);
	}
	else{
		subbagex[w]=1;
		subbag[w]=l;
	}
	for(ii vw : to[u]){
		int v=vw.xx,ww=vw.yy;
		if(v!=pre&&(!block[v])){
			putwt(v,u,w+ww,l+1);
		}
	}
}
void solve(int x){
	dosz(x,x);
	subsz=sz[x];
	int centr=findcentr(x,x);
	block[centr]=1;
	bag.clear();
	bagex.clear();
	// cout << i << '\n' << ans << '\n';
	for(ii sub : to[centr]){
		subbag.clear();
		subbagex.clear();
		int v=sub.xx,ww=sub.yy;
		putwt(v,centr,ww,1);
		// cout << v << "\\\n";

		//K jintei centroid hurtel
		if(subbagex[k]) ans=min(ans,subbag[k]);
		//bag & subbag
		for(auto item : subbag){
			int subw=item.xx,subl=item.yy;
			// cout << bagex[k-subw] << endl;
			if(bagex[k-subw]){
				ans=min(ans,subl+bag[k-subw]);
			}
		}
		for(auto item : subbag){ //merge
			int subw=item.xx,subl=item.yy;
			if(bagex[subw]){
				bag[subw]=min(bag[subw],subl);
			}
			else{
				bagex[subw]=1;
				bag[subw]=subl;
			}
		}
	}
	// cout << '\n' << "######################\n";
	for(ii vw : to[centr]){
		int v=vw.xx;
		if(!block[v]){
			solve(v);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	to.assign(N+1,vector<ii>());
	k=K;
	for(int i=0;i<N-1;i++){
		int u=H[i][0],v=H[i][1],w=L[i];
		to[u].pb(mp(v,w));
		to[v].pb(mp(u,w));
	}
	solve(1);
	// cout << ans << endl;
	// cout << "#################################\n";
	return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57