95pts TLE求卡常
  • 板块P4149 [IOI2011] Race
  • 楼主hy233
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/7/7 15:07
  • 上次更新2023/10/27 21:36:36
查看原帖
95pts TLE求卡常
259300
hy233楼主2022/7/7 15:07
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200005;
const int K=1000005;
const int INF=(1<<30);
inline int rd()
{
	int x=0,f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-') f=0;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<1)+(x<<3)+(ch^48);
	return f?x:-x;
}
int n,k;
vector<pair<int,int> > mp[N];
bool vis[N];

int rt,tot;
int dp[N];
int siz[N];
void getrt(int u,int f)
{
	siz[u]=1;
	dp[u]=0;
	for(int i=0;i<mp[u].size();i++)
	{
		int v=mp[u][i].first;
		if(v==f||vis[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		dp[u]=max(dp[u],siz[v]);
	}
	dp[u]=max(dp[u],tot-siz[u]);
	if(dp[rt]>dp[u])
		rt=u;
}
int ans=INF;
int dis[N],dep[N];
pair<int,int> res[N];
int cnt;
int now[K];
void getdis(int u,int f)
{
	if(dis[u]>k) return;
	res[++cnt]=make_pair(dis[u],dep[u]);
	for(int i=0;i<mp[u].size();i++)
	{
		int v=mp[u][i].first;
		if(v==f||vis[v]) continue;
		dis[v]=dis[u]+mp[u][i].second;
		dep[v]=dep[u]+1;
		getdis(v,u);
	}
}
void dfs(int u)
{
	vis[u]=1;
	int l=1;
	cnt=0;
	for(int i=0;i<mp[u].size();i++)
	{
		int v=mp[u][i].first;
		if(vis[v]) continue;
		dis[v]=mp[u][i].second;
		dep[v]=1;
		getdis(v,u);
		for(int i=l;i<=cnt;i++)
			ans=min(ans,now[k-res[i].first]+res[i].second);
		for(int i=l;i<=cnt;i++)
			now[res[i].first]=min(now[res[i].first],res[i].second);
		l=cnt+1;
	}
	for(int i=1;i<=cnt;i++)
		now[res[i].first]=INF;
	for(int i=0;i<mp[u].size();i++)
	{
		int v=mp[u][i].first;
		if(vis[v]) continue;
		dp[rt=0]=tot=siz[v];
		getrt(v,0);
		dfs(rt);
	}
}
int main()
{
	n=rd(),k=rd();
	for(int i=1;i<n;i++)
	{
		int u=rd(),v=rd(),w=rd();
		mp[u].push_back(make_pair(v,w));
		mp[v].push_back(make_pair(u,w));
	}
	memset(now,0x3f,sizeof(now));
	now[0]=0;
	dp[rt=0]=tot=n;
	getrt(1,0);
	dfs(rt);
	if(ans>=(1<<29))
		cout<<-1<<endl;
	else 
		cout<<ans<<endl;
	return 0;
}
2022/7/7 15:07
加载中...