Submission #1038625

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <string>
#include <cassert>
#define SIZE 200005
#define INF 1000000005

using namespace std;
typedef long long int ll;
typedef pair <ll,int> P;

struct edge
{
	int to,cost;
	edge(int to=0,int cost=0):to(to),cost(cost){}
};
vector <edge> vec[SIZE];
set <P> dp[SIZE];
set <P>::iterator it,its;

void dfs(int v=0,int p=-1,int d=0,ll now=0)
{
	dp[v].clear();
	dp[v].insert(P(now,1));
	ll D=(ll) d+now*2LL;
	for(int i=0;i<vec[v].size();i++)
	{
		edge e=vec[v][i];
		if(e.to!=p)
		{
			dfs(e.to,v,d,now+e.cost);
			if(dp[e.to].size()>dp[v].size()) swap(dp[v],dp[e.to]);
			vector <P> add;
			for(it=dp[e.to].begin();it!=dp[e.to].end();it++)
			{
				P p=*it;
				if(p.first*2LL>=D)
				{
					its=dp[v].lower_bound(P(p.first,-1));
					add.push_back(P(p.first,(its==dp[v].end()?0:its->second)+p.second));
				}
				else add.push_back(p);
				its=dp[v].lower_bound(P(D-p.first,-1));
				ll t1=p.first;
				int t2=p.second;
				if(its!=dp[v].end()) t1=min(t1,its->first),t2+=its->second;
				//if(v==0) printf("%d %d : %lld %d\n",v,e.to,t1,t2);
				add.push_back(P(t1,t2));
			}
			for(int j=0;j<add.size();j++)
			{
				P p=add[j];
				it=dp[v].lower_bound(P(p.first,-1));
				if(it!=dp[v].end()&&it->second>p.second) continue;
				while(1)
				{
					it=dp[v].lower_bound(P(p.first+1,-1));
					if(it==dp[v].begin()) break;
					it--;
					if(it->second<=p.second) dp[v].erase(it);
					else break;
				}
				dp[v].insert(p);
			}
		//printf("%d\n",v);
		//for(it=dp[v].begin();it!=dp[v].end();it++) printf("[%lld %d] ",it->first,it->second);puts("");
		}
	}
}
int main()
{
	int n,K;
	scanf("%d %d",&n,&K);
	assert(n<=40000);
	for(int i=0;i<n-1;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);a--,b--;
		vec[a].push_back(edge(b,c));
		vec[b].push_back(edge(a,c));
	}
	//dfs(0,-1,3,0);
	//it=dp[0].begin();
	///printf("%d\n",it->second);
	//return 0;
	int l=-1,r=INF;
	while(r-l>1)
	{
		int m=(l+r)/2;
		dfs(0,-1,m,0);
		it=dp[0].begin();
		int nm=it->second;
		if(nm>=K) l=m;
		else r=m;
	}
	printf("%d\n",l);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:81:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&K);
                      ^
./Main.cpp:86:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&a,&b,&c);a--,b--;
                             ^

Judge Result