Submission #15681

#	Time	Username	Problem	Language	Result	Execution time	Memory
15681		progressive	Race (IOI11_race)	C++14	0 / 100	13 ms	12944 KiB

race

#include "race.h"
#include <vector>
#include <queue>
#include <set>
#include <cstdio>
#include <algorithm> 
using namespace std;
static const int MAXN=262144;

static set<int> conn[MAXN];
static int H[MAXN][2];
static int L[MAXN];
static int N,K;
//N: number of city K: length of course, H, L:city and cost

static int size[MAXN];
static int maxchild[MAXN];
vector<int> ele;
int dfs(int v,int pa)
{
	ele.push_back(v);
	size[v]=1;
	maxchild[v]=0;
	for(int Eno:conn[v])
	{
		int target=H[Eno][0]^H[Eno][1]^v;
		if(target==pa) continue;
		int ret=dfs(target,v);
		maxchild[v]=max(maxchild[v],ret);
		size[v]+=ret;
	}
	return size[v];
}
int findcentroid(int v)
{
	ele.clear();
	int SZ=dfs(v,-1);
	int minv=987654321;
	int mini=v;
	for(int a:ele)
	{
		int asize=max(maxchild[a],SZ-size[a]);
		if(minv>asize)
		{
			minv=asize;
			mini=a;
		}
	}
	return mini; //amolang
}
static int ans=987654231;
//saving first and second minimum value, while first and second color is different;
int fminv[1010101];
int fminc[1010101];
int sminv[1010101];
int sminc[1010101];
vector<int> dists;
void bktk(int a,int pa,int dist,int height,int color)
{
	if(dist>K) return; //do not have to think about it
	dists.push_back(dist);
	if(fminv[dist]>height)
	{
		if(fminc[dist]!=color)
		{
			sminv[dist]=fminv[dist];
			sminc[dist]=fminc[dist];
		}
		fminv[dist]=height;
		fminc[dist]=color;
	}
	else if(sminv[dist]>height)
	{
		sminv[dist]=height;
		sminc[dist]=color;
	}
	for(int Eno: conn[a])
	{
		int target=H[Eno][0]^H[Eno][1]^a;
		int distadd=L[Eno];
		if(target==pa) continue;
		bktk(target,a,dist+distadd,height+1,color);
	}
}
void work(int v)
{
	dists.clear();
	for(int Eno: conn[v])
	{
		int target=H[Eno][0]^H[Eno][1]^v;
		int dist=L[Eno];
		bktk(target,v,dist,1,target);
	}
	sort(dists.begin(),dists.end());
	dists.resize(unique(dists.begin(),dists.end())-dists.begin());
	for(int x:dists)
	{
		if(fminc[x]!=fminc[K-x])
			ans=min(ans,fminv[x]+fminv[K-x]);
		ans=min(ans,fminv[x]+sminv[K-x]);
	}
	for(int i:dists)
	{
		fminv[i]=sminv[i]=0x3f3f3f3f;
		fminc[i]=-1,sminc[i]=-2;	
	}
	ans=min(ans,fminv[K]);
}
int best_path(int N, int K, int H[][2], int L[])
{
	::N=N, ::K=K;
	for(int i=0;i<N-1;i++)
	{
		::H[i][0]=H[i][0];
		::H[i][1]=H[i][1];
		::L[i]=L[i];
		conn[H[i][0]].insert(i);
		conn[H[i][1]].insert(i);
	}
	for(int i=0;i<=K;i++)
	{
		fminv[i]=sminv[i]=0x3f3f3f3f;
		fminc[i]=-1,sminc[i]=-2;
	}
	queue<int> Q;
	Q.push(0);
	while(!Q.empty())
	{
		int v=Q.front();
		Q.pop();
		int centroid=findcentroid(v);
		work(centroid);
		for(int v:conn[centroid])
		{
			int target=H[v][0]^H[v][1]^centroid;
			conn[target].erase(v);
			Q.push(target);
		}
		conn[centroid].clear();
	}
	if(ans>N) return -1;
	return ans;
}

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