/* "If I can run I will run , If I can walk I will walk , If I can crawl I will crawl" */
/* " But I will NEVER_STOP " */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
using namespace std;
using namespace __gnu_pbds;
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define NeverSpot cout.tie(NULL);
// #define int long long
#define double long double
#define f first
#define s second
#define ed <<endl;
#define co cout<<
#define ci cin>>
#define sped <<" ";
#define sp <<" "<<
#define love cout<<" Insha " ed
#define all(x) (x).begin(),(x).end()
#define fl(a,b) for (int i=a;i<(b);++i)
#define rfl(a,b) for (int i=a;i>=(b);--i)
#define sl(a,b) for (int j=a;j<(b);++j)
#define rsl(a,b) for (int j=a;j>=(b);--j)
#define tl(a,b) for (int k=a;k<(b);++k)
#define rtl(a,b) for (int k=a;k>=(b);--k)
#define test(t) int t;cin>>t;for(int O=1;O<=t;O++)
#define sortv(v) sort(all(v));
#define sumv(arr) accumulate(all(arr),0LL)
#define rev(v) reverse(all(v));
#define ai(o,size) vi o;fl(0,size){int p ; cin>>p ; (o).push_back(p);}
#define Mod 1000000007ll
#define Emod 998244353ll
#define inf 1000000000000000009ll
#define gcd __gcd
inline int Sqrt(int x){ int y=static_cast<long long>(sqrt(x))+5;while(y*y>x)y--;return y;}
#define log2(x) (64 - __builtin_clzll(x) - 1) // log2 in O(1) time
using mii = map<long long, long long>;
using vi = vector<long long>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<long long>>;
using vvp = vector<vector<pair<long long, long long>>>;
using pii = pair<long long, long long>;
using vp = vector<pair<long long, long long>>;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_set; // find_by_order, order_of_key
typedef tree<pair<int,int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_multiset; // find_by_order, order_of_key
string al="abcdefghijklmnopqrstuvwxyz";
//.........For Taking Mod............//
inline int power(int a, int b, int mod=Mod) {int res = 1; while (b > 0) {if (b & 1)res = res * a % mod; a = a * a % mod; b = b >> 1;} return res;}
class mod
{
static int mminvprime(int a, int b) {return power(a, b - 2, b);}
public:
int m=Mod;
void set(int m) {this->m=m;}
int add(int a, int b) {a = a % m; b = b % m; return ((a + b) % m + m) % m;}
int mul(int a, int b) {a = a % m; b = b % m; return (a * b % m + m) % m;}
int sub(int a, int b) {a = a % m; b = b % m; return ((a - b) % m + m) % m;}
int div(int a, int b) {a = a % m; b = b % m; return (mul(a, mminvprime(b, m)) + m) % m;} //only for prime m
}mod;
//.........Bit_Manipulation...........//
#define msb(mask) (63-__builtin_clzll(mask)) /// 0 -> -1
#define lsb(mask) __builtin_ctzll(mask) /// 0 -> 64
#define cntsetbit(mask) __builtin_popcountll(mask)
#define checkbit(mask,bit) ((mask >> bit) & 1ll)
#define onbit(mask,bit) ((mask)|(1LL<<(bit)))
#define offbit(mask,bit) ((mask)&~(1LL<<(bit)))
#define changebit(mask,bit) ((mask)^(1LL<<bit))
// random number generator #BESTEST_QUAILTY :)
// mt19937_64 gen(random_device{}());
// long long rng(int l=0,int r=INT64_MAX){uniform_int_distribution dist(l, r);return dist(gen);}
//
// // Custom hashing for unordered map or set
// const int RANDOM = rng();
// struct chash{int operator()(int x) const { return x ^ RANDOM; }};
// Function
#define Ceil(a,b) ((a+b-1)/b)
#define print(arr) for(auto &o:(arr)){co o sped;} cout ed
#define mxe(v) *max_element(v.begin(),v.end()) // find max element in vector
#define mne(v) *min_element(v.begin(),v.end()) // find min element in vector
inline bool isPrime(int v) {if(v==1) return false; if(v <= 3)return true;if ( v % 2 == 0 || v % 3 == 0)return false;int i = 5;while (i * i <= v) {if (v % i == 0 || v % (i + 2) == 0)return false;i += 6;}return true;}
inline void printbin(int v,int upto=10) {cout<<v<<"-> ";for (int i = upto; i >= 0; --i) {cout<<checkbit(v,i) sped}cout ed}
bool isEqual(double a, double b, double epsilon = 1e-9) {return abs(a - b) <= epsilon * (1ll + max(abs(a), abs(b)));}
inline bool limit_check(long long a, long long b, int max_bits = 59) {if (a == 0 || b == 0) return true;return msb(a) + msb(b) >= 128 - max_bits;}
namespace std {
// fast swap
void swap(order_set &a, order_set &b) { a.swap(b); }
void swap(order_multiset &a, order_multiset &b) { a.swap(b); }
}
// Free to use :}
class Tree {
public:
int n;
vector<vector<pair<int,int>>> e;
vector<vector<int>> lift;
vector<int> start, end, dist, par,depth;
bool Build = false, initialized = false;
int timer = 0;
Tree(int n) : n(n), e(n + 1),depth(n+1), lift(n + 1, vector<int>(20, -1)),
start(n + 1), end(n + 1), dist(n + 1, 0), par(n + 1) {
initialized = true;
}
void addEdge(int u, int v,int w=1) {
if (!initialized) {
co "Tree not initialized" ed;
exit(0);
}
e[u].emplace_back(v,w);
e[v].emplace_back(u,w);
}
void parentOf(int v, int p,int w=1) {
e[v].emplace_back(p,w);
e[p].emplace_back(v,w);
}
void build(int root = 1) {
dfs(root, root);
Build = true;
for (int step = 1; step < 20; step++) {
for (int i = 1; i <= n; i++) {
if (lift[i][step - 1] != -1)
lift[i][step] = lift[lift[i][step - 1]][step - 1];
}
}
}
void dfs(int v, int p) {
par[v] = p;
start[v] = timer++;
for (auto [child,w] : e[v]) {
if (child == p) continue;
dist[child] = dist[v] + w;
depth[child] = depth[v] + 1;
lift[child][0] = v;
dfs(child, v);
}
end[v] = timer;
}
int up(int node, int step) const {
if (!Build) {
co "Build must be called before using `up`" ed;
exit(0);
}
fl(0, 20) {
if (checkbit(step, i) && node != -1)
node = lift[node][i];
}
return node;
}
int lca(int a, int b) const {
if (!Build) {
co "Build must be called before using `lca`" ed;
exit(0);
}
if (is_ancestor(a, b)) return a;
if (is_ancestor(b, a)) return b;
int maxStep = log2(n);
for (int step = maxStep; step >= 0; step--) {
if (lift[a][step] != -1 && !is_ancestor(lift[a][step], b)) {
a = lift[a][step];
}
}
return lift[a][0];
}
int distance(const int x, const int y) const {
return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}
bool is_ancestor(int par, int child) const {
return (start[par] <= start[child] && end[child] <= end[par]);
}
};
class CTree {
public:
int n = 0;
int root = -1;
vector<vector<pair<int,int>>> e, g;
vi subtree_size;
vb is_removed;
int ans=INT_MAX;
int k;
CTree(int n) : n(n), e(n + 1), g(n + 1), subtree_size(n + 1, 0), is_removed(n + 1, false) {}
void addEdge(int u, int v,int w=1) {
e[u].push_back({v,w});
e[v].push_back({u,w});
}
int get_subtree_size(int node, int parent = -1) {
subtree_size[node] = 1;
for (auto& child : e[node] | views::keys) {
if (child == parent || is_removed[child]) {
continue;
}
subtree_size[node] += get_subtree_size(child, node);
}
return subtree_size[node];
}
int get_centroid(int node, int tree_size, int parent = -1) {
for (auto& child : e[node] | views::keys) {
if (child == parent || is_removed[child]) {
continue;
}
if (subtree_size[child] * 2 > tree_size) {
return get_centroid(child, tree_size, node);
}
}
return node;
}
void cal(int v,int p,mii &data,bool filling,int depth=0,int dis=0) {
if (filling) {
if (data.contains(dis)) {
data[dis]=min(static_cast<int>(data[dis]),depth);
}else {
data[dis]=depth;
}
}else {
int want=k-dis;
if (data.contains(want)) {
ans=min(ans,static_cast<int>(data[want])+depth);
}
}
for (auto &[child,w] : e[v]) {
if (is_removed[child] || child==p) { continue; }
cal(child,v,data,filling,depth+1,dis+w);
}
}
void build(int node = 1,int p = -1) {
int centroid = get_centroid(node, get_subtree_size(node));
is_removed[centroid] = true;
mii data;
data[0]=0;
for (auto &[child,w] : e[centroid]) {
if (is_removed[child] || child==p) { continue; }
cal(child, centroid, data, false,1,w);
cal(child, centroid, data, true,1,w);
}
for (auto child : e[centroid] | views::keys) {
if (is_removed[child]) {
continue;
}
build(child, centroid);
}
}
};
int best_path(int n, int k, int edges[][2], int weights[]) {
if (k == 1) { return 0; }
ci n>>k;
CTree ct(n);
fl(0,n-1) {
auto &[x,y]=edges[i];
int w=weights[i];
ct.addEdge(x,y,w);
}
ct.k=k;
ct.build();
int ans=ct.ans;
if (ans==INT_MAX)ans=-1;
return ans;
}
// int main() {
// int n, k;
// ci n>>k;
// int edges[n][2], weights[n];
// fl(0,n-1) {
// int u, v, w;
// ci u>>v>>w;
// edges[i][0]=u, edges[i][1]=v;
// weights[i]=w;
// }
//
// cout<<best_path(n, k, edges, weights)<<endl;
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |