| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 940391 | JakobZorz | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
#include<random>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
int n,q;
vector<pair<int,int>>nodes[500000];
int par[500000][20];
int depth1[500000];
ll depth[500000];
void dfs(int node,int p){
par[node][0]=p;
for(int i=1;i<20;i++)
par[node][i]=par[par[node][i-1]][i-1];
for(auto[ne,w]:nodes[node]){
if(ne==p)
continue;
depth[ne]=depth[node]+w;
depth1[ne]=depth1[node]+1;
dfs(ne,node);
}
}
int get_parent(int node,int p){
for(int i=0;i<20;i++){
if(p&(1<<i)){
node=par[node][i];
}
}
return node;
}
int lca(int a,int b){
if(depth1[a]<depth1[b])
swap(a,b);
a=get_parent(a,depth1[a]-depth1[b]);
for(int i=19;i>=0;i--){
if(par[a][i]!=par[b][i]){
a=par[a][i];
b=par[b][i];
}
}
if(a!=b)
a=par[a][0];
return a;
}
ll dist(int a,int b){
int l=lca(a,b);
return depth[a]+depth[b]-2*depth[l];
}
void solve(){
int n,q;
cin>>n>>q;
for(int i=0;i<n-1;i++){
int a,b,c;
cin>>a>>b>>c;
nodes[a].emplace_back(b,c);
nodes[b].emplace_back(a,c);
}
dfs(0,0);
while(q--){
int n1,n2;
cin>>n1>>n2;
vector<int>arr1(n1),arr2(n2);
for(int&i:arr1)
cin>>i;
for(int&i:arr2)
cin>>i;
ll res=1e18;
for(int i1=0;i1<n1;i1++){
for(int i2=0;i2<n2;i2++){
res=min(res,dist(arr1[i1],arr2[i2]));
}
}
cout<<res<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
//freopen("/Users/jakob/cp_testing/test.txt","r",stdin);freopen("output.out","w",stdout);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
/*
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
*/