제출 #67307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67307		zetapi	경주 (Race) (IOI11_race)	C++14	100 / 100	906 ms	108444 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]+maps[K+2*Weight[CurrentRoot]-Weight[node]]-height[CurrentRoot]);
	}
	if(Weight[node]-Weight[CurrentRoot]==K)
		res=min(res,height[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))
		{
	//		cout<<node<<" "<<Weight[node]<<"\n";
			res=min(res,maps[Weight[node]+K]-height[node]);
		}
	}
	//cout<<"cuurent node "<<node<<"\n";
	//for(auto A:maps)
	//	cout<<A.first<<" "<<A.second<<"\n";
	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)
		maps.clear();
	else if(Special[par]!=node)
		maps.clear();
	else
		relax(Weight[node],height[node]);
	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;
}
 
/*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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57