| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 888271 | ash_gamertable | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
// C++
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int ans=1e9,N;
vector<vector< pair<int,int> > > g;// {node,dist}
vector<int> off;
void dfs(int node,int par,vector<map<int,int> > &hash,int k)
{
//cerr<<node<<" * "<<par<<"\n";
for(auto x:g[node])
{
if(x.first==par) continue;
dfs(x.first,node,hash,k);
}
for(auto child:g[node])
{
if(child.first == par) continue;
int off_node = off[node],off_child=off[child.first],edge=child.second,off_used=off_child;
if(hash[node].size()<hash[child.first].size())
{
// cout<<node<<"*\n";
off_used = off[node];
off[node] = off_child+edge;
edge=0;
swap(hash[node],hash[child.first]);
}
for(auto it=hash[child.first].begin();it!=hash[child.first].end();it++)
{
int dist = it->first + off_used + edge;
int mn_nodes = it->second;
if(hash[node].find(k-dist-off[node])!=hash[node].end())
ans=min(ans,mn_nodes+hash[node][k-dist-off[node]]);
if(hash[node].find(dist-off[node])!=hash[node].end())
{
int v1 = hash[node][dist-off[node]];
hash[node][dist-off[node]] = min(v1,1+mn_nodes);
}
else hash[node][dist-off[node]] = 1+mn_nodes;
}
}
// if(node==2)
// {
// for(auto it=hash[node].begin();it!=hash[node].end();it++){
// cout<<it->first<<" "<<it->second<<"\n";
// }
// cout<<off[node]<<"\n";
// }
// cerr<<node<<" "<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,k,a,b,wt;
vector<map<int,int> > hash;
cin>>n>>k;
g.resize(n+10);
off.assign(n+10,0);
for(int i=1;i<=n-1;i++){
cin>>a>>b>>wt;
a++,b++;
g[a].push_back(make_pair(b,wt));
g[b].push_back(make_pair(a,wt));
}
hash.resize(n+10);
for(int i=1;i<=n;i++) hash[i][0]=1;
dfs(1,0,hash,k);
if(ans==1 || ans==1e9) ans=0;
ans--;
cout<<ans<<"\n";
return 0;
}