| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1044621 | june0501 | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
using namespace std;
using ll [[maybe_unused]] = long long;
using ull [[maybe_unused]] = unsigned long long;
using lll [[maybe_unused]] = __int128;
using lld [[maybe_unused]] = long double;
using llld [[maybe_unused]] = __float128;
template<typename T> using graph [[maybe_unused]] = vector<vector<pair<int,T>>>;
template<typename T> using matrix [[maybe_unused]] = vector<vector<T>>;
class CentroidTree {
int n, root;
int MAX_BIT;
graph<int> g;
vector<int> sz, // size of the subtree
depth, // depth of the node
tree, // centroid tree(tree[i] = parent of i at the centroid tree)
S, T, E; // Euler Tour
vector<ll> dist; // distance from the initial root
int pw = 0;
int dfs(int u, int p) {
sz[u] = 1;
E[++pw] = u;
S[u] = pw;
for (const auto& [v, w]: g[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
sz[u] += dfs(v, u);
E[++pw] = u;
}
return sz[u];
}
vector<int> pw2, lg2;
vector<vector<pair<int,int>>> ST;
void lca_prepare(){
pw2.resize(MAX_BIT);
pw2[0] = 1;
for (int i = 1; i < MAX_BIT; i++) pw2[i] = pw2[i - 1] << 1;
lg2.resize(n * 2);
fill(lg2.begin(), lg2.end(), -1);
for (int i = 0; i < MAX_BIT; i++) if (pw2[i] < n * 2) lg2[pw2[i]] = i;
for (int i = 1; i < n * 2; i++) if (lg2[i] == -1) lg2[i] = lg2[i - 1];
ST.resize(MAX_BIT, vector<pair<int,int>>(n * 2));
for (int i = 1; i < n * 2; i++) ST[0][i] = {depth[E[i]], E[i]};
for(int k = 1; k < MAX_BIT; k++) {
for (int i = 1; i < n * 2; i++) {
if (i + pw2[k - 1] > n * 2) continue;
ST[k][i] = min(ST[k - 1][i], ST[k - 1][i + pw2[k - 1]]);
}
}
}
int lca(int u, int v) {
int l = S[u], r = S[v];
if (l > r) swap(l, r);
int k = lg2[r - l + 1];
return min(ST[k][l], ST[k][r - pw2[k] + 1]).second;
}
ll get_dist(int u, int v) {
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
int get_centroid(int u) {
for (const auto& [v, w]: g[u]) {
if (sz[u] >> 1 < sz[v] && sz[v] < sz[u]) {
sz[u] -= sz[v];
sz[v] += sz[u];
return get_centroid(v);
}
}
return u;
}
void build_centroid_tree(int u, int p = -1) {
u = get_centroid(u);
if (p == -1) tree[u] = u;
else tree[u] = p;
for (const auto& [v, _]: g[u])
if (sz[v] < sz[u])
build_centroid_tree(v, u);
}
public:
explicit
CentroidTree(const graph<int>& g, int root = 1) : g(g), n((int)g.size()), root(root) {
sz.resize(n, 0);
depth.resize(n, 0);
dist.resize(n, 0);
S.resize(n), T.resize(n), E.resize(n * 2);
tree.resize(n);
MAX_BIT = std::ceil(std::log2(n));
dfs(root, -1);
lca_prepare();
build_centroid_tree(root);
x_dist.resize(n, 1e18);
y_dist.resize(n, 1e18);
}
vector<ll> x_dist, y_dist;
ll ans = 1e18;
void query(int u, bool x) {
// climb up the centroid tree and update ancestor's set
if (x) {
for (int v = u;; v = tree[v]) {
x_dist[v] = min(x_dist[v], get_dist(u, v));
if (tree[v] == v) break;
}
} else {
for (int v = u;; v = tree[v]) {
y_dist[v] = min(y_dist[v], get_dist(u, v));
if (x_dist[v] != (ll) 1e18) ans = min(ans, x_dist[v] + y_dist[v]);
if (tree[v] == v) break;
}
}
}
void clear() {
x_dist.assign(n, 1e18);
y_dist.assign(n, 1e18);
ans = 1e18;
}
}; // class CentroidTree
int32_t main() {
fastIO;
int n, q;
cin >> n >> q;
graph<int> g(n + 1);
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u+1].emplace_back(v+1, w);
g[v+1].emplace_back(u+1, w);
}
CentroidTree solver(g);
while (q--) {
int s, t;
cin >> s >> t;
vector<int> x(s), y(t);
for (auto &e : x) cin >> e;
for (auto &e : y) cin >> e;
// Problem: For a ∈ x, b ∈ y, find the min dist(a, b).
solver.clear();
for (const auto &e : x) solver.query(e+1, true);
for (const auto &e : y) solver.query(e+1, false);
cout << solver.ans << endl;
}
return 0;
}