#include <bits/stdc++.h>
typedef unsigned short u16;
typedef short i16;
typedef unsigned int u32;
typedef int i32;
typedef unsigned long long u64;
typedef long long i64;
typedef float f32;
typedef double f64;
typedef long double f80;
typedef long double f128;
template <typename T>
using limits = std::numeric_limits<T>;
struct custom_hash
{
static unsigned long long splitmix64(unsigned long long x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
std::size_t operator()(unsigned long long x) const
{
static const unsigned long long rand_time = std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + rand_time);
}
};
i32 lg2(u64 x) { return 8 * sizeof(u64) - __builtin_clzll(x); }
typedef std::vector<std::vector<std::pair<u64, u64>>> AdjList;
const u64 bs = 20;
class Sparse
{
protected:
AdjList adj;
std::vector<u64> tin, tout, dist;
std::unordered_map<u64, u64, custom_hash> tour;
u64 timer = 0;
std::array<std::array<u64, 1000005>, bs> tb;
u64 min_dist(u64 a, u64 b) { return dist[a] < dist[b] ? a : b; }
u64 get(u64 l, u64 r)
{
auto lg_len = lg2(r - l + 1);
return min_dist(tb[lg_len][l], tb[lg_len][r - (1 << lg_len) + 1]);
}
public:
void init(u64 n)
{
adj.resize(n);
tin.assign(n, 0);
tout.assign(n, 0);
dist.assign(n, 0);
}
void add(int a, int b, int d)
{
adj[a].emplace_back(b, d);
adj[b].emplace_back(a, d);
}
void euler(u64 u, u64 prev)
{
tin[u] = timer++;
tour[timer] = u;
for (auto &[v, w] : adj[u])
{
if (v != prev)
{
dist[v] = dist[u] + w;
euler(v, u);
tour[++timer] = u;
}
}
tout[u] = timer;
}
void build()
{
for (u64 i = 1; i <= timer; ++i)
{
tb[0][i] = tour[i];
}
for (u64 i = 1; i < bs; i++)
{
for (u64 j = 1; j + (1ULL << i) - 1 <= timer; j++)
{
tb[i][j] = min_dist(tb[i - 1][j], tb[i - 1][j + (1ULL << (i - 1))]);
}
}
}
bool is_parent(u64 u, u64 v) { return tin[u] < tin[v] && tout[v] < tout[u]; }
u64 lca(u64 u, u64 v)
{
if (is_parent(u, v))
{
return u;
}
if (is_parent(v, u))
{
return v;
}
if (tin[u] > tout[v])
{
return get(tout[v], tin[u]);
}
return get(tout[u], tin[v]);
}
u64 gtin(u64 x) { return tin[x]; }
u64 gdist(u64 u, u64 v)
{
auto c = lca(u, v);
return (dist[u] - dist[c]) + (dist[v] - dist[c]);
}
};
Sparse inst;
const i64 INF = 1e15;
void Init(int N, int A[], int B[], int D[])
{
inst.init(N);
for (int i = 0; i < N - 1; i++)
{
inst.add(A[i], B[i], D[i]);
}
inst.euler(0, limits<u64>::max());
inst.build();
}
long long Query(int S, int X[], int T, int Y[])
{
std::unordered_map<i32, i64, custom_hash> r1, r2, r3;
std::vector<int> ord;
int sz = S + T;
ord.reserve(sz);
for (int i = 0; i < S; i++)
{
r1[X[i]] = 0;
r2[X[i]] = INF;
r3[X[i]] = 0;
ord.push_back(X[i]);
}
for (int i = 0; i < T; i++)
{
if (r1.contains(Y[i]))
{
return 0;
}
r1[Y[i]] = 1;
r2[Y[i]] = 0;
r3[Y[i]] = INF;
ord.push_back(Y[i]);
}
std::sort(ord.begin(), ord.end(), [](int a, int b) { return inst.gtin(a) < inst.gtin(b); });
for (int i = 1; i < sz; ++i)
{
int c = inst.lca(ord[i], ord[i - 1]);
if (!r1.contains(c))
{
r1[c] = 2;
r2[c] = r3[c] = INF;
ord.push_back(c);
}
}
ord.resize(std::unique(ord.begin(), ord.end()) - ord.begin());
std::sort(ord.begin(), ord.end(), [](int a, int b) { return inst.gtin(a) < inst.gtin(b); });
std::unordered_map<int, std::vector<std::pair<u64, u64>>> vtree;
std::stack<int> st;
for (u64 i = 0; i < ord.size(); i++)
{
if (st.empty())
{
st.push(ord[i]);
continue;
}
while (!st.empty() && !inst.is_parent(st.top(), ord[i]))
{
st.pop();
}
if (!st.empty())
{
vtree[st.top()].emplace_back(static_cast<u64>(ord[i]), inst.gdist(st.top(), ord[i]));
}
st.push(ord[i]);
}
std::function<void(u64, u64)> dfs_vtree = [&](u64 u, u64 prev)
{
for (auto &[v, w] : vtree[u])
{
if (v != prev)
{
dfs_vtree(v, u);
r2[u] = std::min(r2[u], r2[v] + static_cast<i64>(w));
r3[u] = std::min(r3[u], r3[v] + static_cast<i64>(w));
}
}
};
dfs_vtree(ord[0], limits<u64>::max());
i64 res = INF;
for (u64 i = 0; i < ord.size(); ++i)
{
res = std::min(res, r2[ord[i]] + r3[ord[i]]);
}
return res;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:162:16: error: 'class std::unordered_map<int, long long int, custom_hash>' has no member named 'contains'
162 | if (r1.contains(Y[i]))
| ^~~~~~~~
factories.cpp:177:17: error: 'class std::unordered_map<int, long long int, custom_hash>' has no member named 'contains'
177 | if (!r1.contains(c))
| ^~~~~~~~
