| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 573829 | 79brue | 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;
typedef long long ll;
const ll INF = 1e18;
int n, q;
vector<pair<int, ll> > link[500002];
int in[500002], idx[500002], par[500002], inCnt;
int LCADB[500002][20];
ll dist[500002];
int depth[500002];
int centroidRoot;
int centroidPar[500002];
bool centroidUsed[500002];
int subTreeSize[500002];
ll nearest[500002];
void dfs(int x, int p = -1){
in[++inCnt] = x, idx[x] = inCnt;
for(auto y: link[x]){
if(y.first==p) continue;
par[y.first] = x;
dist[y.first] = dist[x] + y.second;
depth[y.first] = depth[x] + 1;
dfs(y.first, x);
}
}
void makeLCA(){
for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}
int getLCA(int x, int y){
if(depth[x] > depth[y]) swap(x, y);
for(int d=0; d<20; d++) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
if(x==y) return x;
for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
return par[x];
}
ll ndist(int x, int y){
return dist[x] + dist[y] - dist[getLCA(x, y)] * 2;
}
void dfsCentroid(int x, int p = -1){
subTreeSize[x] = 1;
for(auto y: link[x]){
if(centroidUsed[y.first] || y.first == p) continue;
dfsCentroid(y.first, x);
subTreeSize[x] += subTreeSize[y.first];
}
}
int secondDfs(int x, int lim, int p = -1){
for(auto y: link[x]){
if(centroidUsed[y.first] || y.first == p) continue;
if(subTreeSize[y.first] >= p) return secondDfs(y.first, lim, x);
}
return x;
}
int getCentroid(int x){
dfsCentroid(x);
int c = secondDfs(x, (subTreeSize[x]+1) / 2);
x = c;
centroidUsed[x] = 1;
for(auto y: link[x]){
if(centroidUsed[y.first]) continue;
int tmp = getCentroid(y.first);
centroidPar[tmp] = x;
}
return x;
}
void addPoint(int x){
int org = x;
while(x){
nearest[x] = min(nearest[x], ndist(x, org));
x = centroidPar[x];
}
}
void delPoint(int x){
while(x){
nearest[x] = INF;
x = centroidPar[x];
}
}
ll findAns(int x){
int org = x;
ll ret = INF;
while(x){
ret = min(ret, nearest[x] + ndist(org, x));
x = centroidPar[x];
}
return ret;
}
int main(){
scanf("%d %d", &n, &q);
for(int i=1; i<n; i++){
int x, y; ll c;
scanf("%d %d %lld", &x, &y, &c);
x++, y++;
link[x].push_back(make_pair(y, c));
link[y].push_back(make_pair(x, c));
}
for(int i=1; i<=n; i++) nearest[i] = INF;
dfs(1);
makeLCA();
centroidRoot = getCentroid(1);
while(q--){
int A, B;
scanf("%d %d", &A, &B); /// A들에 대해 가장 가까운 B 찾기
vector<int> avec(A), bvec(B);
for(int i=0; i<A; i++) scanf("%d", &avec[i]), avec[i]++;
for(int i=0; i<B; i++) scanf("%d", &bvec[i]), bvec[i]++, addPoint(bvec[i]);
ll ans = INF;
for(auto x: avec) ans = min(ans, findAns(x));
printf("%lld\n", ans);
for(auto x: bvec) delPoint(x);
}
}