| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1281749 | ducanh0811 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
// 🌲🌲🌲🌲🌲🌳🌳🌳🌳🌳🌳🌴🌴🌴🌴🌴🌴🌴🌴
#include <bits/stdc++.h>
bool M1;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;
#define MAXN 500005
#define MAXQ 100005
int n, q;
vector<pair<int, int>> g[MAXN];
bool blocked[MAXN];
int sz[MAXN];
int par[MAXN];
int dep[MAXN];
int sumWeight[MAXN];
int curWeight[MAXN];
int up[MAXN][20];
int bestVal[MAXN];
const int INF = 1e15;
///++++++++++++++++++++++++++++++++++++++///
void minimize(int &a, const int &b) {
if (a > b) a = b;
}
void preCalc(int u, int p) {
for (pair<int, int> &x : g[u]) {
int v, w; tie(v, w) = x;
if (v == p) continue;
up[v][0] = u;
dep[v] = dep[u] + 1;
sumWeight[v] = sumWeight[u] + w;
curWeight[v] = w;
preCalc(v, u);
}
}
void prepareLCA() {
FOR(j, 1, 19) FOR(i, 1, n) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int h = dep[a] - dep[b];
for (int i = 0; (1 << i) <= h; ++i) {
if (h >> i & 1) a = up[a][i];
}
if (a == b) return a;
h = __lg(dep[a]);
for (int i = h; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
int dist(int a, int b) {
int lca = LCA(a, b);
return sumWeight[a] + sumWeight[b] - 2 * sumWeight[lca];
}
void calc(int u, int p) {
sz[u] = 1;
for (pair<int, int> &x : g[u]) {
int v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
calc(v, u);
sz[u] += sz[v];
}
}
int FindCentroid(int u, int p, int SZ) {
for (pair<int, int> &x : g[u]) {
int v, w; tie(v, w) = x;
if (blocked[v] || v == p) continue;
if (sz[v] > SZ) return FindCentroid(v, u, SZ);
}
return u;
}
void decompose(int curNode, int preCentroid) {
calc(curNode, 0);
int c = FindCentroid(curNode, 0, sz[curNode] / 2);
par[c] = preCentroid;
blocked[c] = true;
for (pair<int, int> &x : g[c]) {
int v, w; tie(v, w) = x;
if (blocked[v]) continue;
decompose(v, c);
}
}
void update(int curNode) {
int fixed = curNode;
while (curNode != 0) {
minimize(bestVal[curNode], dist(fixed, curNode));
curNode = up[curNode][0];
}
}
void reset(int curNode) {
int fixed = curNode;
while (curNode != 0) {
bestVal[curNode] = 1e15;
curNode = up[curNode][0];
}
}
int query(int curNode) {
int fixed = curNode;
int res = INF;
while (curNode != 0) {
minimize(res, bestVal[curNode] + dist(curNode, fixed));
curNode = up[curNode][0];
}
return res;
}
void solve() {
cin >> n >> q;
FOR(i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w;
u++; v++;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
preCalc(1, 0);
prepareLCA();
decompose(1, 0);
FOR(i, 1, n) bestVal[i] = 1e15;
FOR(Nium, 1, q) {
int S, T; cin >> S >> T;
vector<int> tmpNode;
FOR(i, 1, S) {
int curNode; cin >> curNode;
curNode++;
update(curNode);
tmpNode.push_back(curNode);
}
int res = INF;
FOR(i, 1, T) {
int curNode; cin >> curNode;
curNode++;
minimize(res, query(curNode));
}
for (int &curNode : tmpNode) reset(curNode);
cout << res << '\n';
}
}
///++++++++++++++++++++++++++++++++++++++///
#define task "test"
int32_t main() {
if (fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
bool M2;
cerr << "++++++++++++++++++++++++++++\n";
cerr << "Time: " << clock() << "ms" << '\n';
cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
cerr << "++++++++++++++++++++++++++++\n";
return 0;
}