| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 287473 | Namnamseo | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }
typedef pair<int,ll> pil;
vector<pil> edge[500010];
vector<int> comp[500010];
int par[20][500010];
ll depth[500010];
int d2 [500010];
int n,q;
void in(){
read(n,q);
for(int i=1; i<n; ++i){
int a,b; ll d; read(a,b,d);
edge[a].pb({b,d}); edge[b].pb({a,d});
}
}
int tin[500010];
int nt;
void dfs(int x){
tin[x]=nt++;
for(auto& yp:edge[x]){
int y=yp.first; ll d=yp.second;
if(par[0][x] != y){
par[0][y] = x;
depth[y] = depth[x] + d;
d2[y] = d2[x]+1;
dfs(y);
}
}
}
int lca(int a,int b){
if(d2[a]>d2[b]) swap(a,b);
int df=d2[b]-d2[a];
for(int i=18; 0<=i; --i) if(1&(df>>i)) b=par[i][b];
for(int i=18; 0<=i; --i) if(par[i][a]!=par[i][b])
a=par[i][a], b=par[i][b];
if(a!=b) a=par[0][a];
return a;
}
void sparse(){
par[0][0] = -1;
for(int i=1; i<=18; ++i) for(int j=0; j<n; ++j){
int t=par[i-1][j];
if(t==-1) par[i][j]=-1;
else par[i][j]=par[i-1][t];
}
}
bool isPar(int a,int b){
if(d2[a]>d2[b]) return false;
int df=d2[b]-d2[a];
for(int i=18; 0<=i; --i){
if(1&(df>>i)) b=par[i][b];
}
return a==b;
}
ll dA[500010];
ll dB[500010];
vector<int> hist;
void compress(vector<int>& pts){
stack<int> stk;
hist.clear();
for(int p : pts){
comp[p].clear();
while(stk.size() && !isPar(stk.top(), p))
hist.pb(stk.top()), stk.pop();
if(stk.size()) comp[stk.top()].pb(p);
stk.push(p);
}
while(stk.size()) hist.pb(stk.top()), stk.pop();
}
ll inf=(1LL<<60);
int main(){
in(); dfs(0); sparse();
for(;q--;){
int A, B;
read(A, B);
vector<int> pa(A), pb(B), pts;
for(int i=0; i<A; ++i) read(pa[i]);
for(int i=0; i<B; ++i) read(pb[i]);
for(int x:pa) pts.pb(x);
for(int x:pb) pts.pb(x);
auto timecomp = [&](const int& a, const int& b){
return tin[a]<tin[b];
};
sort(all(pts), timecomp);
int sz=A+B;
for(int i=1; i<sz; ++i) pts.pb(lca(pts[i-1], pts[i]));
sort(all(pts), timecomp);
pts.erase(unique(all(pts)), pts.end());
compress(pts);
for(int x:pts) dA[x]=dB[x]=inf;
for(int x:pa) dA[x]=0;
for(int x:pb) dB[x]=0;
ll ans=inf;
for(int x:hist){
for(int y:comp[x]){
dA[x] = min(dA[x], dA[y]+depth[y]-depth[x]);
dB[x] = min(dB[x], dB[y]+depth[y]-depth[x]);
}
ans=min(ans, dA[x]+dB[x]);
}
printf("%lld\n", ans);
}
return 0;
}