| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 869448 | SUNWOOOOOOOO | Factories (JOI14_factories) | C++17 | 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.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pint = array <int, 2>;
const LL mxN = 500005, INF = 1e18;
LL n, q, mnval[mxN], treesz[mxN], maxtree[mxN], cpar[mxN];
vector <pint> adj[mxN];
vector <LL> new_vst, ans;
struct lca {
LL par[20][mxN], dep[mxN], len[mxN];
void dfs(int now, int parent){
par[0][now] = parent;
for (pint elm : adj[now]){
if (elm[0] == parent) continue;
dep[elm[0]] = dep[now] + 1;
len[elm[0]] = len[now] + elm[1];
dfs(elm[0], now);
}
}
void init(){
dfs(1, 1);
for (int i = 1; i < 20; i++){
for (int j = 1; j <= n; j++){
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}
int get_lca(int x, int y){
if (x == y) return x;
if (dep[x] < dep[y]) swap(x, y);
int dif = dep[x] - dep[y];
for (int i = 0; dif; i++){
if (dif & 1) x = par[i][x];
dif /= 2;
}
for (int i = 19; i >= 0; i--){
if (par[i][x] != par[i][y]){
x = par[i][x], y = par[i][y];
}
}
if (x == y) return x;
else return par[0][x];
}
LL get_dist(int x, int y){
return len[x] + len[y] - 2 * len[get_lca(x, y)];
}
} lca;
void get_size(int now, int parent){
new_vst.push_back(now);
treesz[now] = 1, maxtree[now] = 0;
for (pint elm : adj[now]){
if (elm[0] == parent || cpar[elm[0]]) continue;
get_size(elm[0], now);
treesz[now] += treesz[elm[0]];
maxtree[now] = max(maxtree[now], treesz[elm[0]]);
}
}
int get_centroid(int x){
new_vst.clear();
get_size(x, x);
LL cent_pos = -1, cent_res = INF;
for (int elm : new_vst){
maxtree[elm] = max(maxtree[elm], treesz[x] - treesz[elm]);
if (maxtree[elm] < cent_res){
cent_pos = elm;
cent_res = maxtree[elm];
}
}
return cent_pos;
}
void build_centroid(int x, int parent){
x = get_centroid(x);
cpar[x] = parent;
for (pint elm : adj[x]){
if (cpar[elm[0]]) continue;
build_centroid(elm[0], x);
}
}
int main()
{
scanf("%lld %lld", &n, &q);
for (int i = 0, u, v, d; i < n - 1; i++){ // 1-based
scanf("%d %d %d", &u, &v, &d); u++, v++;
adj[u].push_back({v, d});
adj[v].push_back({u, d});
}
lca.init();
build_centroid(1, -1);
for (int i = 1; i <= n; i++) mnval[i] = INF;
while (q--){
LL sn, tn, ret = INF;
scanf("%lld %lld", &sn, &tn);
for (int i = 0, j, s; i < sn; i++) {
scanf("%d", &s); s++;
for (int j = s; j != -1; j = cpar[j]){
new_vst.push_back(j);
mnval[j] = min(mnval[j], lca.get_dist(j, s));
}
}
for (int i = 0, j, t; i < tn; i++) {
scanf("%d", &t); t++;
for (int j = t; j != -1; j = cpar[j]){
ret = min(ret, mnval[j] + lca.get_dist(j, t));
}
}
ans.push_back(ret);
for (int elm : new_vst) mnval[elm] = INF;
new_vst.clear();
}
for (LL elm : ans) printf("%lld\n", elm);
return 0;
}