提交记录 10622


用户 题目 状态 得分 用时 内存 语言 代码长度
Zhouzj2004 noip18c. 【NOIP2018】赛道修建 Accepted 100 169.944 ms 5684 KB C++ 1.55 KB
提交时间 评测时间
2019-09-21 17:03:36 2020-08-01 02:18:25
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50000

using namespace std;

void read(int &x)
{
	char ch=getchar(); x=0;
	while (ch<'0'||ch>'9') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
}

struct EDGE {int next,to,w; }edge[N*2+1];
int head[N+1],f[N+1],g[N+1],a[N+1],n,m,cnt=1;
bool bz[N+1];

void add(int u,int v,int w){ edge[cnt]=(EDGE){head[u],v,w},head[u]=cnt++; }

void qsort(int l,int r)
{
	int i=l,j=r,mid=a[l+r>>1];
	while (i<=j)
	{
		while (a[i]<mid) ++i;
		while (a[j]>mid) --j;
		if (i<=j) swap(a[i++],a[j--]);
	}
	if (i<r) qsort(i,r);
	if (j>l) qsort(l,j);
}

void dfs(int k,int last,int mid)
{
 	f[k]=g[k]=0; int tot=0;
	for (int i=head[k];i;i=edge[i].next)
	{
		if (edge[i].to==last) continue;
		dfs(edge[i].to,k,mid);
	}
	for (int i=head[k];i;i=edge[i].next)
	{
		if (edge[i].to==last) continue;
		f[k]+=f[edge[i].to];
		a[++tot]=g[edge[i].to]+edge[i].w;
		if (a[tot]>=mid) ++f[k],--tot;
		else bz[tot]=0;
	}
	if (tot==0) return;
	qsort(1,tot);
	for (int i=1;i<=tot;i++)
	{
		if (bz[i]) continue;
		int j=0;
		for (int l=i+1,r=tot,mid1=l+r>>1;l<=r;a[i]+a[mid1]<mid ? l=mid1+1:r=(j=mid1)-1,mid1=l+r>>1);
		while (bz[j]&&j<=tot) ++j;
		if (j>0&&j<=tot) ++f[k],bz[j]=bz[i]=1;
	}
	for (int i=tot;i>=1;i--) 
		if (! bz[i]){
			g[k]=a[i]; break;
		}
}

int main()
{
	read(n),read(m);
	for (int i=1,x,y,z;i<n;i++) read(x),read(y),read(z),add(x,y,z),add(y,x,z);
	int ans=0;
	for (int l=1,r=500000000,mid=l+r>>1;l<=r;mid=(long long)l+r>>1)
	{
		dfs(1,0,mid);
		if (f[1]>=m) l=(ans=mid)+1;
		else r=mid-1;
	}
	printf("%d",ans);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #110.42 us40 KBAcceptedScore: 5

Testcase #216.17 us40 KBAcceptedScore: 5

Testcase #319.62 us40 KBAcceptedScore: 5

Testcase #4614 us84 KBAcceptedScore: 5

Testcase #567.108 ms1 MB + 216 KBAcceptedScore: 5

Testcase #653.319 ms1 MB + 368 KBAcceptedScore: 5

Testcase #781.161 ms1 MB + 216 KBAcceptedScore: 5

Testcase #8136.912 ms1 MB + 992 KBAcceptedScore: 5

Testcase #9633.69 us152 KBAcceptedScore: 5

Testcase #1033.379 ms3 MB + 368 KBAcceptedScore: 5

Testcase #1157.063 ms5 MB + 564 KBAcceptedScore: 5

Testcase #1233.11 us44 KBAcceptedScore: 5

Testcase #1334.35 us44 KBAcceptedScore: 5

Testcase #14112.62 us48 KBAcceptedScore: 5

Testcase #15111.92 us52 KBAcceptedScore: 5

Testcase #16687.42 us88 KBAcceptedScore: 5

Testcase #17801.69 us80 KBAcceptedScore: 5

Testcase #1842.844 ms1 MB + 80 KBAcceptedScore: 5

Testcase #1964.319 ms1 MB + 360 KBAcceptedScore: 5

Testcase #20169.944 ms2 MB + 252 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 09:11:50 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用