Submission #116598

#	Time	Username	Problem	Language	Result	Execution time	Memory
116598		khulegub	Race (IOI11_race)	C++14	0 / 100	3 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,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(subbag.find(w)!=subbag.end()){
		subbag[w]=min(subbag[w],l);
	}
	else{
		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);
	int centr = x;
	block[centr]=1;
	bag.clear();
	// cout << i << '\n' << ans << '\n';
	for(ii sub : to[centr]){
		subbag.clear();
		int v=sub.xx,ww=sub.yy;
		putwt(v,centr,ww,1);
		// cout << v << "\\\n";
		//K jintei centroid hurtel
		if(subbag.find(k)!=subbag.end()) ans=min(ans,subbag[k]);
		//bag & subbag
		for(auto item : subbag){
			int subw=item.xx,subl=item.yy;
			// cout << bagex[k-subw] << endl;
			if(bag.find(k-subw)!=bag.end()){
				ans=min(ans,subl+bag[k-subw]);
			}
		}

		for(auto item : subbag){ //merge
			int subw=item.xx,subl=item.yy;
			if(bag.find(subw)!=bag.end()){
				bag[subw]=min(bag[subw],subl);
			}
			else{
				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(0);
	// cout << ans << endl;
	// cout << "#################################\n";
	return ans;
}

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