| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 553804 | QwertyPi | 공장들 (JOI14_factories) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5 + 13;
const int inf = 1LL << 60;
int tail[N], d[N], p[N], dep[N];
vector<pii> G[N];
void dfs(int v, int par = -1){
int out = 0, son = -1;
for(auto i : G[v]){
if(i.fi != par){
d[i.fi] = d[v] + i.se;
p[i.fi] = v;
dfs(i.fi, v);
out++; son = i.fi;
}
}
tail[v] = v, p[tail[v]] = p[v]; if(v != 0) dep[tail[v]] = dep[p[v]] + 1;
// tail[v] = (out == 1 ? tail[son] : v), p[tail[v]] = p[v], dep[tail[v]] = dep[];
}
void dfs2(int v, int par = -1){
for(auto i : G[v]){
if(i.fi != par){
if(v == tail[v]) dep[tail[i.fi]] = dep[v] + 1;
dfs2(i.fi, v);
}
}
}
struct state{
int v, dis, colour;
bool operator< (const state& o) const{
return v < o.v;
}
};
vector<state> qry[N];
int32_t main(){
// ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for(int i = 0; i < n - 1; i++){
int u, v, w;
cin >> u >> v >> w;
G[u].pb({v, w});
G[v].pb({u, w});
}
dfs(0);
dfs2(0);
for(int i = 0; i < m; i++){
int s, t;
cin >> s >> t;
for(int j = n - 1; j >= 0; j--) qry[j].clear();
for(int j = 0; j < s; j++){
int v; cin >> v;
qry[dep[tail[v]]].pb({tail[v], d[v] - d[tail[v]], 0});
}
for(int j = 0; j < t; j++){
int v; cin >> v;
qry[dep[tail[v]]].pb({tail[v], d[v] - d[tail[v]], 1});
}
int ans = inf;
for(int j = n - 1; j >= 0; j--){
vector<state> tmp;
sort(qry[j].begin(), qry[j].end());
for(auto k : qry[j]){
bool used = false;
if(tmp.size() >= 1 && tmp.back().v == k.v && tmp.back().colour + k.colour == 1) ans = min(ans, tmp.back().dis + k.dis);
if(tmp.size() >= 2 && tmp[tmp.size() - 2].v == k.v && tmp[tmp.size() - 2].colour + k.colour == 1) ans = min(ans, tmp[tmp.size() - 2].dis + k.dis);
if(tmp.size() >= 1 && tmp[tmp.size() - 1].v == k.v && tmp[tmp.size() - 1].colour == k.colour){
tmp[tmp.size() - 1].dis = min(tmp[tmp.size() - 1].dis, k.dis); used = true;
}
if(tmp.size() >= 2 && tmp[tmp.size() - 2].v == k.v && tmp[tmp.size() - 2].colour == k.colour){
tmp[tmp.size() - 2].dis = min(tmp[tmp.size() - 2].dis, k.dis); used = true;
}
if(!used){
tmp.pb(k);
}
}
if(j > 0){
for(auto k : tmp){
qry[j - 1].pb({p[k.v], k.dis + d[k.v] - d[p[k.v]], k.colour});
}
}
}
cout << ans << endl;
}
}