Submission #402469

#	Time	Username	Problem	Language	Result	Execution time	Memory
402469		Jasiekstrz	Race (IOI11_race)	C++17	0 / 100	4 ms	5008 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define fi first
#define se second
using namespace std;
const int NN=2e5;
const int INF=1e9+7;
struct Poss
{
	int val[2],g[2];
	Poss()
	{
		val[0]=val[1]=INF;
		g[0]=g[1]=0;
	}
	void operator+=(pair<int,int> oth)
	{
		int vv=oth.fi,gg=oth.se;
		if(vv<val[0])
		{
			val[1]=val[0];
			g[1]=g[0];
			val[0]=vv;
			g[0]=gg;
		}
		else if(vv<val[1])
		{
			val[1]=vv;
			g[1]=gg;
		}
		return;
	}
	int get(int x)
	{
		return (x==g[0] ? val[1]:val[0]);
	}
};
int k;
vector<pair<int,int>> e[NN+10];
bool vis[NN+10];
int siz[NN+10];
map<int,Poss> mp;
void dfs_siz(int x,int p)
{
	siz[x]=1;
	for(auto v:e[x])
	{
		if(!vis[v.fi] && v.fi!=p)
		{
			dfs_siz(v.fi,x);
			siz[x]+=siz[v.fi];
		}
	}
	return;
}
int centro(int x,int p,int s_all)
{
	for(auto v:e[x])
	{
		if(vis[v.fi] || v.fi==p)
			continue;
		int c=centro(v.fi,x,s_all);
		if(c!=-1)
			return c;
	}
	if(2*siz[x]>=s_all)
		return x;
	return -1;
}
int dfs(int x,int p,int d1,int d2,int id)
{
	int ans=INF;
	ans=min(ans,d2+mp[k-d1].get(id));
	mp[d1]+=make_pair(d2,id);
	for(auto v:e[x])
	{
		if(vis[v.fi] || v.fi==p)
			continue;
		ans=min(ans,dfs(v.fi,x,min(INF,d1+v.se),d2+1,id));
	}
	return ans;
}
int solve(int x)
{
	int ans=INF;
	dfs_siz(x,-1);
	x=centro(x,-1,siz[x]);
	vis[x]=true;
	mp.clear();
	mp[0]+=make_pair(0,x);
	for(auto v:e[x])
	{
		if(!vis[v.fi])
			ans=min(ans,dfs(v.fi,x,v.se,1,v.fi));
	}
	for(auto v:e[x])
	{
		if(!vis[v.fi])
			ans=min(ans,solve(v.fi));
	}
	return ans;
}
int best_path(int N,int K,int H[][2],int L[])
{
	k=K;
	for(int i=0;i<N-1;i++)
	{
		e[H[i][0]].push_back({H[i][1],L[i]});
		e[H[i][1]].push_back({H[i][0],L[i]});
	}
	int ans=solve(0);
	return (ans>=INF ? -1:ans);
}

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