#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
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 u64 splitmix64(u64 x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
std::size_t operator()(u64 x) const
{
static const u64 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) - 1; }
typedef std::vector<std::vector<std::pair<u64, u64>>> AdjList;
#define MAX_N 1000000
#define MAX_2N MAX_N * 2 + 5
const u64 bs = 32;
std::array<std::array<u64, MAX_2N>, bs> tb;
std::array<u64, MAX_N> rtype, r1, r2, tin, tout, dist;
std::array<u64, MAX_2N> tour;
const u64 UDEF = limits<u64>::max();
template <typename T>
std::vector<T> with_capacity(u64 n)
{
std::vector<T> res;
res.reserve(n);
return res;
}
class Sparse
{
protected:
AdjList adj;
u64 timer = 0;
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.assign(n, with_capacity<decltype(adj)::value_type::value_type>(n)); }
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 = 1e18;
u64 N;
void Init(int _N, int A[], int B[], int D[])
{
N = _N;
inst.init(N);
for (u64 i = 0; i < N - 1; ++i)
{
inst.add(A[i], B[i], D[i]);
}
inst.euler(0, UDEF);
inst.build();
rtype.fill(UDEF);
}
long long Query(int S, int X[], int T, int Y[])
{
std::vector<int> ord;
int sz = S + T;
ord.reserve(sz);
for (int i = 0; i < S; i++)
{
rtype[X[i]] = 0;
r1[X[i]] = INF;
r2[X[i]] = 0;
ord.push_back(X[i]);
}
for (int i = 0; i < T; i++)
{
if (rtype[Y[i]] != UDEF)
{
return 0;
}
rtype[Y[i]] = 1;
r1[Y[i]] = 0;
r2[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)
{
i64 c = inst.lca(ord[i], ord[i - 1]);
if (rtype[c] == UDEF)
{
rtype[c] = 2;
r1[c] = r2[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); });
AdjList vtree(N, with_capacity<decltype(vtree)::value_type::value_type>(N));
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);
r1[u] = std::min(r1[u], r1[v] + w);
r2[u] = std::min(r2[u], r2[v] + w);
}
}
};
dfs_vtree(ord[0], limits<u64>::max());
u64 res = INF;
for (u64 i = 0; i < ord.size(); ++i)
{
res = std::min(res, r1[ord[i]] + r2[ord[i]]);
rtype[ord[i]] = UDEF;
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
1002 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
1122 ms |
18120 KB |
Output is correct |
| 4 |
Correct |
1004 ms |
18364 KB |
Output is correct |
| 5 |
Correct |
912 ms |
18616 KB |
Output is correct |
| 6 |
Correct |
776 ms |
18196 KB |
Output is correct |
| 7 |
Correct |
1045 ms |
18108 KB |
Output is correct |
| 8 |
Correct |
1024 ms |
18412 KB |
Output is correct |
| 9 |
Correct |
919 ms |
18684 KB |
Output is correct |
| 10 |
Correct |
787 ms |
18300 KB |
Output is correct |
| 11 |
Correct |
1042 ms |
19136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
8404 KB |
Output is correct |
| 2 |
Execution timed out |
8051 ms |
244524 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
8660 KB |
Output is correct |
| 2 |
Correct |
1002 ms |
18276 KB |
Output is correct |
| 3 |
Correct |
1122 ms |
18120 KB |
Output is correct |
| 4 |
Correct |
1004 ms |
18364 KB |
Output is correct |
| 5 |
Correct |
912 ms |
18616 KB |
Output is correct |
| 6 |
Correct |
776 ms |
18196 KB |
Output is correct |
| 7 |
Correct |
1045 ms |
18108 KB |
Output is correct |
| 8 |
Correct |
1024 ms |
18412 KB |
Output is correct |
| 9 |
Correct |
919 ms |
18684 KB |
Output is correct |
| 10 |
Correct |
787 ms |
18300 KB |
Output is correct |
| 11 |
Correct |
1042 ms |
19136 KB |
Output is correct |
| 12 |
Correct |
8 ms |
8404 KB |
Output is correct |
| 13 |
Execution timed out |
8051 ms |
244524 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
