Submission #1163260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163260		boclobanchat	Race (IOI11_race)	C++20	0 / 100	4 ms	9032 KiB

race

#include"race.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=2e5+5;
vector<ii> ds[MAXN];
bool ck[MAXN];
int sub[MAXN],D[MAXN*5],ans=1e9,k;
vector<int> vv;
vector<ii> vi;
void dfs(int i,int pre)
{
	sub[i]=1;
	for(auto v:ds[i]) if(v.fi!=pre&&!ck[v.fi])
	{
		dfs(v.fi,i);
		sub[i]+=sub[v.fi];
	}
}
int centroid(int i,int pre,int c)
{
	for(auto v:ds[i]) if(v.fi!=pre&&!ck[v.fi]&&sub[v.fi]*2>c) return centroid(v.fi,i,c);
	return i;
}
void solve(int i,int pre,int d,int e)
{
	if(d>k) return ;
	if(D[k-d]!=1e9) ans=min(ans,e+D[k-d]);
	vi.push_back({d,e});
	for(auto v:ds[i]) if(v.fi!=pre&&!ck[v.fi]) solve(v.fi,i,d+v.se,e+1);
}
void decomp(int i)
{
	dfs(i,i);
	int pos=centroid(i,i,sub[i]);
	ck[pos]=true,D[0]=0;
	for(auto v:ds[pos]) if(!ck[v.fi])
	{
		solve(v.fi,i,v.se,1);
		for(auto v:vi) vv.push_back(v.fi),D[v.fi]=min(D[v.fi],v.se);
		vi.clear();
	}
	for(auto v:vv) D[v]=1e9;
	vv.clear();
	for(auto v:ds[pos]) if(!ck[v.fi]) decomp(v.fi);
}
int best_path(int N,int K,int H[][2],int L[])
{
	k=K;
	for(int i=0;i<=1e6;i++) D[i]=1e9;
	for(int i=0;i<N-1;i++)
	{
		ds[H[i][0]].push_back({H[i][1],L[i]});
		ds[H[i][1]].push_back({H[i][0],L[i]});
	}
	decomp(1);
	if(ans==1e9) return -1;
	return ans;
}

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