| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 766544 | nnhzzz | Race (IOI11_race) | C++17 | 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.
// -------------------------Solution by Stormgamming------------------------- //
/* Author: Nguyen Ngoc Hung, Ngo Gia Tu high school */
/*
Tips:
1.int? long long?
2.don't submit wrong answer
3.figure out logic first, then start writing please
4.know about the range
5.check if you have to input t or not
6.modulo of negative numbers is not a%b, it is a%b + abs(b)
7.special cases (n=1?)
*/
//-------------------------------------------------------------//
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <bitset>
#include <math.h>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <string>
#include <fstream>
#include <iterator>
using namespace std;
//-------------------------------------------------------------//
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O2")
#pragma GCC optimization ("O3")
*/
//-------------------------------------------------------------//
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define vpii vector<pair<int,int>>
#define vvvi vector<vector<vector<int>>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define di deque<int>
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define endl "\n"
#define mask(i) (1ll<<i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define uni(a) ((a).erase(unique(all(a)),(a).end()))
#define se second
#define DEBUG(X) {auto _X=(X); cerr << "L" << __LINE__ << ": " << #X << " = " << (_X) << endl;}
#define reset(x,val) memset((x),(val),sizeof(x))
#define bit(i,j) ((i>>j)&1ll)
#define ull unsigned long long
#define ll long long
#define ld long double
// #define int long long
#define fi first
#define __Storgamming__ signed main()
#define repdis(i,be,en,j) for(int i = (be); i<=(en); i+=j)
#define repd(i,be,en) for(int i = (be); i>=(en); i--)
#define rep(i,be,en) for(int i = (be); i<=(en); i++)
#define file(name) if(fopen(name".inp", "r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
//-------------------------------------------------------------//
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(ld x) {cerr << x;}
void __print(ull x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x?"true":"false");}
//-------------------------------------------------------------//
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
template<class T> inline T sqr(T x) {return x*x;};
//-------------------------------------------------------------//
bool mem2;
const int N = (int)1e6+1;
const int SIZE = (int)1e6+10;
const int maxn = (int)1e6+7;
const int MOD = (int)1e9+7;
const int oo = (int)1e9+7;
const int base = (int)311;
const ld PI = (ld)3.1415926535897932384626433832795;
const ld EPS = (ld)1e-9;
//-------------------------------------------------------------//
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
struct CENROID{
set<pii> adj[maxn];
int check[maxn],cnt_edge[maxn],sz[maxn];
int n,k,times;
void add(int u, int v, int w){
adj[u].insert({v,w});
adj[v].insert({u,w});
}
int dfs(int u, int dad){
sz[u] = 1;
for(auto [v,w]:adj[u]){
if(v!=dad){
sz[u] += dfs(v,u);
}
}
return sz[u];
}
int centroid(int u, int dad, int nn){
for(auto [v,w]:adj[u]){
if(v!=dad){
if(sz[v]>nn/2){
return centroid(v,u,nn);
}
}
}
return u;
}
int dfs1(int u, int dad, int dis, int cnt, int t, vpii& tmp){
int need = k-dis,res = oo;
if(need>=0 && check[need]==t){
mini(res,cnt+cnt_edge[need]);
}
if(dis<=k){
tmp.push_back({dis,cnt});
for(auto [v,w]:adj[u]){
if(v!=dad){
mini(res,dfs1(v,u,dis+w,cnt+1,t,tmp));
}
}
}
return res;
}
int solve(int u, int dad){
int nn = dfs(u,dad);
int c = centroid(u,dad,nn);
int t = ++times,res = oo;
check[0] = t;
cnt_edge[0] = 0;
for(auto [v,w]:adj[c]){
vpii tmp;
mini(res,dfs1(v,c,w,1,t,tmp));
for(auto [dis,cnt]:tmp){
if(check[dis]!=t || (check[dis]==t && cnt_edge[dis]>cnt)){
check[dis] = t;
cnt_edge[dis] = cnt;
}
}
}
vpii tmp(all(adj[c]));
for(auto it:tmp){
adj[c].erase(it);
adj[it.fi].erase({c,it.se});
mini(res,solve(it.fi,c));
}
return res;
}
CENROID(int _n, int _k):n(_n),k(_k){
times = 0;
}
};
void solve(){
int n,k;
cin >> n >> k;
CENROID g(n,k);
rep(i,2,n){
int u,v,w;
cin >> u >> v >> w;
g.add(u,v,w);
}
int res = g.solve(0,-1);
if(res==oo){
res = -1;
}
cout << res;
}
bool mem1;
//-------------------------------------------------------------//
__Storgamming__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int test = 1;
while(test--){
solve();
}
cerr << "Memory Cost: " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB" << endl;
cerr << "Time Cost: " << clock() * 1000. / CLOCKS_PER_SEC << "MS" << endl;
return 0;
}