| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 161002 | ArshiaDadras | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* In the name of Allah */
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18 + 5;
const int N = 5e5 + 5, LG = 18 + 2;
int n, q, h[N], st[N], en[N], par[N][LG];
vector<pair<int, int>> adj[N];
int n1, n2, u1[N], u2[N];
long long dist[N];
struct Segment {
long long seg[N << 2];
bool mark[N];
Segment() {
memset(seg, 63, sizeof seg);
}
void update(int p, long long x, int id = 1, int st = 0, int en = n) {
if (en - st == 1) {
seg[id] = x;
return;
}
int mid = st + en >> 1;
if (p < mid)
update(p, x, id << 1, st, mid);
else
update(p, x, id << 1 | 1, mid, en);
seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}
long long get(int l, int r, int id = 1, int st = 0, int en = n) {
if (r <= st || en <= l)
return INF;
if (l <= st && en <= r)
return seg[id];
int mid = st + en >> 1;
return min(get(l, r, id << 1, st, mid), get(l, r, id << 1 | 1, mid, en));
}
void clear(int id = 1, int st = 0, int en = n) {
if (seg[id] >= INF)
return;
seg[id] = INF;
if (en - st == 1) {
mark[st] = false;
return;
}
int mid = st + en >> 1;
clear(id << 1, st, mid);
clear(id << 1 | 1, mid, en);
}
} seg1, seg2;
inline int lca(int u, int v) {
if (h[u] > h[v])
swap(u, v);
for (int i = LG - 1; ~i; i--)
if (h[v] - h[u] >> i & 1)
v = par[v][i];
for (int i = LG - 1; ~i; i--)
if (par[u][i] ^ par[v][i]) {
u = par[u][i];
v = par[v][i];
}
return u ^ v? par[u][0]: u;
}
void dfs(int u) {
static int time = 0;
for (int i = 0; i < LG - 1; i++)
par[u][i + 1] = par[par[u][i]][i];
st[u] = time++;
for (auto v: adj[u])
if (v.first ^ par[u][0]) {
h[v.first] = h[par[v.first][0] = u] + 1;
dist[v.first] = dist[u] + v.second;
dfs(v.first);
}
en[u] = time;
}
inline bool cmp(int u, int v) {
return st[u] < st[v];
}
inline void read_input() {
cin >> n >> q;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
inline void solve() {
long long ans = INF;
sort(u1, u1 + n1, cmp);
sort(u2, u2 + n2, cmp);
seg1.clear(), seg2.clear();
for (int i = 0; i < n1; i++)
seg1.update(st[u1[i]], dist[u1[i]]);
for (int i = 0; i < n2; i++)
seg2.update(st[u2[i]], dist[u2[i]]);
for (int i = 0, p = 0; i < n1; i++) {
ans = min(ans, seg2.get(st[u1[i]], en[u1[i]]) - dist[u1[i]]);
while (p < n2 && !cmp(u1[i], u2[p]))
p++;
if (p < n2) {
int x = lca(u1[i], u2[p]);
ans = min(ans, dist[u1[i]] + seg2.get(st[x], en[x]) - 2 * dist[x]);
}
}
for (int i = 0, p = 0; i < n2; i++) {
ans = min(ans, seg1.get(st[u2[i]], en[u2[i]]) - dist[u2[i]]);
while (p < n1 && !cmp(u2[i], u1[p]))
p++;
if (p < n1) {
int x = lca(u2[i], u1[p]);
ans = min(ans, dist[u2[i]] + seg1.get(st[x], en[x]) - 2 * dist[x]);
}
}
cout << ans << endl;
}
inline void write_output() {
for (dfs(0); q--; solve()) {
cin >> n1 >> n2;
for (int i = 0; i < n1; i++)
cin >> u1[i];
for (int i = 0; i < n2; i++)
cin >> u2[i];
}
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
read_input(), write_output();
return 0;
}