| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1292538 | sonarcht | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef map<ll,ll> mll;
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll N = 1e5 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans, a[N];
vector<pll> adj[N];
ll p[N], timer = 0, tin[N], tout[N], d[N], up[N][21], mx[N][21];
void dfs(ll p, ll u) {
tin[u] = ++timer;
for (auto [v,w] : adj[u]) {
if (v == p) continue;
d[v] = d[u] + w;
up[v][0] = u;
mx[v][0] = w;
for (int j = 1; j <= 20; ++j) {
up[v][j] = up[up[v][j-1]][j-1];
mx[v][j] = max(mx[up[v][j-1]][j-1], mx[v][j-1]);
}
dfs(u, v);
}
tout[u] = timer;
}
bool is_anc(ll u, ll v) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll lca(ll u, ll v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int j = 20; j >= 0; --j) {
if (up[u][j] && !is_anc(up[u][j], v)) u = up[u][j];
}
return up[u][0];
}
vector<pll> aux[N];
ll mark[N], dist[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;
bool cmp(ll a, ll b) {
return tin[a] < tin[b];
}
void dijkstra(vll& v) {
for (ll s : v) {
dist[s] = 0;
pq.push({0, s});
}
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (dist[u] != d) continue;
for (auto [v,w] : aux[u]) {
if (d+w < dist[v]) {
dist[v] = d+w;
pq.push({d+w, v});
}
}
}
}
void solve() {
cin >> n >> q;
for (int i = 1; i < n; ++i) {
ll x, y, w;
cin >> x >> y >> w;
++x, ++y;
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
dfs(-1, 1);
fill(dist, dist+N, inf);
while (q--) {
ll s, t;
cin >> s >> t;
vll v, v1, v2;
for (int i = 1; i <= s; ++i) {
ll x;
cin >> x;
++x;
v.push_back(x);
v1.push_back(x);
mark[x] = 1;
}
for (int i = 1; i <= t; ++i) {
ll x;
cin >> x;
++x;
v.push_back(x);
v2.push_back(x);
mark[x] = 2;
}
sort(v.begin(), v.end(), cmp);
for (ll i = 0; i < s+t-1; ++i) v.push_back(lca(v[i], v[i+1]));
sort(v.begin(), v.end(), cmp);
v.erase(unique(v.begin(), v.end()), v.end());
stack<ll> st;
for (ll u : v) {
while (!st.empty() && !is_anc(st.top(), u)) st.pop();
if (!st.empty()) {
ll p = st.top(), w = d[u] - d[p];
aux[u].push_back({p, w});
aux[p].push_back({u, w});
}
st.push(u);
}
dijkstra(v1);
ans = inf;
for (ll u : v) {
if (mark[u] == 2) ans = min(ans, dist[u]);
}
cout << ans << endl;
for (ll u : v) {
aux[u].clear();
mark[u] = 0;
dist[u] = inf;
}
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(".INP", "r")) {
freopen(".INP", "r", stdin);
freopen(".OUT", "w", stdout);
}
ll testCase = 1;
// cin >> testCase;
while (testCase--) {
solve();
}
return 0;
}