提交记录 12860


用户 题目 状态 得分 用时 内存 语言 代码长度
luosiyuan noip18c. 【NOIP2018】赛道修建 Time Limit Exceeded 80 1 s 575 MB + 104 KB C++11 1.19 KB
提交时间 评测时间
2020-06-13 19:46:18 2020-08-01 03:00:32
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cassert>
#include<set>
using namespace std;
struct Edge{
	int to,next,value;
}e[100005];
int n,h[50005],m,cnt,ans;
void Add_Edge(int x,int y,int z){
	e[++cnt].to=y;
	e[cnt].next=h[x],e[cnt].value=z;
	h[x]=cnt;
}
int Check(int nnow,int fa,int mid){
	multiset<int> s;
	for(int i=h[nnow];i;i=e[i].next){
		int y=e[i].to;
		if(y==fa)continue;
		int tmp=Check(y,nnow,mid)+e[i].value;
	//	cout<<tmp<<endl;
		if(tmp>=mid)ans++;
		else s.insert(tmp);
	}
	int maxx=0;
	while(!s.empty()){
		int now=*s.begin();
		if(s.size()==1){
			return max(maxx,now);
		}
		auto k=s.lower_bound(mid-now);
	//	cout<<maxx<<endl;
		if(k==s.begin()&&s.count(*k)==1)k++;
		if(k==s.end()){
			maxx=max(maxx,now);
			s.erase(s.find(now));
		}
		else {
			ans++;
			s.erase(s.find(now));
			s.erase(s.find(*k));
		}
	}
	return maxx;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		Add_Edge(x,y,z);
		Add_Edge(y,x,z);
	}
	int l=1,r=5e8,anss=-1;
	//Check(1,0,31);
	//cout<<ans<<endl;
	while(l<=r){
		int mid=(l+r)/2;
		ans=0;
		Check(1,0,mid);
		if(ans>=m)anss=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",anss);
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #139.92 us44 KBAcceptedScore: 5

Testcase #250.63 us44 KBAcceptedScore: 5

Testcase #365.31 us44 KBAcceptedScore: 5

Testcase #41.14 ms92 KBAcceptedScore: 5

Testcase #5190.885 ms2 MB + 220 KBAcceptedScore: 5

Testcase #698.558 ms1 MB + 892 KBAcceptedScore: 5

Testcase #71 s2 MB + 216 KBTime Limit ExceededScore: 0

Testcase #81 s3 MB + 672 KBTime Limit ExceededScore: 0

Testcase #9875.76 us212 KBAcceptedScore: 5

Testcase #1038.366 ms4 MB + 980 KBAcceptedScore: 5

Testcase #1169.209 ms8 MB + 240 KBAcceptedScore: 5

Testcase #1280.5 us44 KBAcceptedScore: 5

Testcase #1379.55 us44 KBAcceptedScore: 5

Testcase #14222.27 us48 KBAcceptedScore: 5

Testcase #15222.11 us60 KBAcceptedScore: 5

Testcase #161.146 ms104 KBAcceptedScore: 5

Testcase #171.48 ms88 KBAcceptedScore: 5

Testcase #1857.609 ms920 KBAcceptedScore: 5

Testcase #191 s1 MB + 828 KBTime Limit ExceededScore: 0

Testcase #20149.518 ms575 MB + 104 KBRuntime ErrorScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2020-08-05 16:08:34 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用