#include <bits/stdc++.h>
#ifndef LOCAL
#include "grader.h"
#endif
using namespace std;
inline void fileIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
inline void read() {}
template <class S>
inline void read(S &arg) {
cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
while (Lptr != Rptr) {
read(*Lptr);
Lptr++;
}
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
read(arg);
read(rest...);
}
inline void write() {}
template <class S>
inline void write(S arg) {
cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char del = ' ') {
if (Lptr != Rptr) {
write(*Lptr);
Lptr++;
}
while (Lptr != Rptr) {
write(del);
write(*Lptr);
Lptr++;
}
}
template <class S, class... T>
inline void write(S arg, T... rest) {
write(arg);
write(' ');
write(rest...);
}
#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
template <class T, class S>
inline bool smin(T &a, S b) {
return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
return a < (T)b ? a = b, 1 : 0;
}
constexpr int MOD = 1e9 + 7;
constexpr int N = 2e5 + 10;
template <typename T>
inline T mod(T &v) {
return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
return mod(l += r);
}
ll po(ll v, ll u) {
return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}
int H[N][2], L[N], sz[N];
int ans = 1e9, k;
vi adj[N];
int vec[N];
bitset<N> alive;
int mp[(int)1e6 + 10];
void predfs(int v, int par = -1) {
sz[v] = 1;
for (auto e : adj[v]) {
int u = H[e][0] ^ H[e][1] ^ v;
if (alive[u] && u ^ par) {
predfs(u , v);
sz[v] += sz[e];
}
}
}
int cent(int v, int s = -1,int par = -1) {
if (s == -1) s = sz[v];
int mx = s - sz[v];
for (auto e : adj[v]) {
int u = H[e][0] ^ H[e][1] ^ v;
if (alive[u] && u ^ par) {
smax(mx , sz[u]);
int local = cent(u , s , v);
if (~local) return local;
}
}
if (mx <= (s / 2)) return v;
return -1;
}
void dfs1(int v, int par, int dist, int dist2 = 1) {
if (dist > k) return;
if (~mp[k - dist]) smin(ans , mp[k - dist] + dist2);
for (auto e : adj[v]) {
int u = H[e][0] ^ H[e][1] ^ v;
if (alive[u] && u ^ par)
dfs1(u , v , dist + L[e] , dist2 + 1);
}
}
void dfs2(int v, int par, int dist, int dist2 = 1) {
if (dist > k) return;
if (~mp[dist]) smin(mp[dist] , dist2);
else {
mp[dist] = dist2;
vec[R++] = dist;
}
for (auto e : adj[v]) {
int u = H[e][0] ^ H[e][1] ^ v;
if (alive[u] && u ^ par)
dfs2(u , v , dist + L[e] , dist2 + 1);
}
}
void solve(int v) {
predfs(v);
alive[v = cent(v)] = false;
auto f = [v]() {
reverse(all(adj[v]));
for (auto e : adj[v]) {
int u = H[e][0] ^ H[e][1] ^ v;
if (alive[u]) {
dfs1(u, v, L[e]);
dfs2(u, v, L[e]);
}
}
if (~mp[k]) smin(ans , mp[k]);
rep(i , 0 , R) mp[vec[i]] = -1;
R = 0;
};
f();
f();
for (auto e : adj[v]) {
int u = H[e][0] ^ H[e][1] ^ v;
if (alive[u]) solve(u);
}
}
int best_path(int n, int k2, int H2[][2], int L2[]) {
memset(mp , -1, sizeof(mp));
k = k2;
rep(i , 0 , n - 1) {
H[i][0] = H2[i][0];
H[i][1] = H2[i][1];
L[i] = L2[i];
adj[H[i][0]].pb(i);
adj[H[i][1]].pb(i);
}
alive.set();
solve(0);
if (ans > n) ans = -1;
return ans;
}
Compilation message
race.cpp:3:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
