Submission #67303

#	Time	Username	Problem	Language	Result	Execution time	Memory
67303		zetapi	Race (IOI11_race)	C++14	0 / 100	10 ms	7628 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 

const int MAX=3e5;
const ll  INF=1e9;

typedef pair<ll,ll> pii;

map<ll,ll> maps;

vector<pii> later,vec[MAX];

ll K,res,height[MAX],SubSize[MAX],Special[MAX],Weight[MAX];

void Prepare(int node,int par,int hei)
{
	SubSize[node]=1;
	height[node]=hei;
	for(auto A:vec[node])
	{
		if(A.first==par)
			continue;
		Weight[A.first]=Weight[node]+A.second;
		Prepare(A.first,node,hei+1);
		SubSize[node]+=SubSize[A.first];
	}
	pii cur=mp(-1,-1);
	for(auto A:vec[node])
	{
		if(A.first==par)
			continue;
		cur=max(cur,mp(SubSize[A.first],A.first));
	}
	Special[node]=cur.second;
	return ;
}

void relax(ll x,ll y)
{
	if(maps.count(x))
		maps[x]=min(maps[x],y);
	else
		maps[x]=y;
}

void cal(int node,int par,int CurrentRoot)
{
	later.pb(mp(Weight[node],height[node]));
	if(maps.count(K+2*Weight[CurrentRoot]-Weight[node]))
	{
		//cout<<CurrentRoot<<" "<<node<<" "<<Weight[CurrentRoot]<<" "<<Weight[node]<<" required more "<<K+2*Weight[CurrentRoot]-Weight[node]<<"\n";
		res=min(res,height[node]-height[CurrentRoot]+1+maps[K+2*Weight[CurrentRoot]-Weight[node]]-height[CurrentRoot]);
	}
	for(auto A:vec[node])
	{
		if(A.first==par)
			continue;
		cal(A.first,node,CurrentRoot);
	}
	return ;
}

void dfs(int node,int par)		
{
	for(auto A:vec[node])
	{
		if(A.first==par or Special[node]==A.first)
			continue;
		dfs(A.first,node);
	}
	if(Special[node]>=0)
	{
		dfs(Special[node],node);
		if(maps.count(Weight[node]+K))
			res=min(res,maps[Weight[node]+K]-height[node]+1);
	}
	relax(Weight[node],height[node]);
	for(auto A:vec[node])
	{
		if(A.first==par or A.first==Special[node])
			continue;
		cal(A.first,node,node);	
		for(auto A:later)
			relax(A.first,A.second);
		later.clear();
	}
	if(par>=0)
		if(Special[par]!=node)
			maps.clear();
	return ;
}

int best_path(int N,int K_,int H[][2],int L[])
{
	K=K_;
 	for(int A=0;A<N-1;A++)
 	{
 		vec[H[A][0]].pb(mp(H[A][1],L[A]));
 		vec[H[A][1]].pb(mp(H[A][0],L[A]));
 	}
 	res=INF;
 	Prepare(0,-1,0);
 	dfs(0,-1);
 	if(res==INF)
 		res=-1;
 	return res-1;
}

/*int main()
{
	ios_base::sync_with_stdio(false);

	
	int N=11,K=12;
	int 		   L[]={3,
					    4,
					    5,
					    4,
						6,
						3,
						2,
						5,
						6,
						7};
	int H[][2]={{0,1},
				{0,2},
				{2,3},
				{3,4},
				{4,5},
				{0,6},
				{6,7},
				{6,8},
				{8,9},
				{8,10}};

	//N=4,K=3;
	//int H[][2]={{0,1},{1,2},{1,3}},L[]={1,2,4};
	cout<<best_path(N,K,H,L);
	return 0;
}*/

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