| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 235363 | Atalasion | Factories (JOI14_factories) | C++14 | 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.
//khodaya khodet komak kon
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int N = 500000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000010;
const ll LOG = 20;
int n, q, mark[N], mark2[N], st[N], ft[N], Time, par[N][LOG], hh[N];
ll h[N], dis[N];
vector<pii> G[N];
vector<pair<int, ll>> g[N];
void DFS(int v = 1, int p = 0){
par[v][0] = p;
st[v] = ++Time;
for (int lg = 1; lg < LOG; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1];
for (auto u:G[v]){
if (u.F == p) continue;
h[u.F] = h[v] + u.S;
hh[u.F] = hh[v] + 1;
DFS(u.F, v);
}
ft[v] = Time;
}
int LCA(int v, int u){
if (hh[v] < hh[u]) swap(v, u);
int res = hh[v] - hh[u];
for (int i = 0; i < LOG; i++){
if (res & (1 << i)) v = par[v][i];
}
if (v == u) return v;
for (int i = LOG - 1; i >= 0; i--){
if (par[v][i] != par[u][i]) v = par[v][i], u = par[u][i];
}
return par[v][0];
}
void Init(int &n, vi A, vi B, vi D){
for (int i = 0; i < n - 1; i++){
B[i] ++, A[i] ++;
G[A[i]].pb({B[i], D[i]});
G[B[i]].pb({A[i], D[i]});
}
DFS();
}
bool cmp(int x, int y){
return st[x] < st[y];
}
void DJ(vi Y, vi node){
for (auto u:node) dis[u] = INF;
set<pair<ll, int>> st;
for (auto u:Y) dis[u] = 0, st.insert({0, u});
while (st.size()){
pair<ll, int> fr = *st.begin();
// cout << fr.F << ' ' << fr.S << '\n';
st.erase(st.begin());
for (auto u:g[fr.S]){
// cout << "YES " << u.F << ' ' << dis[u.F] << ' ' << fr.F << ' ' << fr.S << '\n';
if (dis[u.F] > fr.F + u.S){
st.erase({dis[u.F], u.F});
dis[u.F] = fr.F + u.S;
st.insert({dis[u.F], u.F});
}
}
}
}
ll Query(int S, vi X, int T, vi Y){
vector<int> node;
for (int i = 0; i < S; i++) X[i]++;
for (int i = 0; i < T; i++) Y[i] ++;
for (auto u:X) node.pb(u), mark[u] = 1;
for (auto u:Y) node.pb(u), mark2[u] = 1;
sort(all(node), cmp);
int SZ = node.size();
for(int i = 1; i < SZ; i++){
node.pb(LCA(node[i - 1], node[i]));
// cout << node[i - 1] << ' ' << node[i] << ' ' << LCA(node[i - 1], node[i]) << '\n';
}
sort(all(node), cmp);
stack<int> SS;
SS.push(node[0]);
SZ =node.size();
for (int i = 1; i < SZ; i++){
while (ft[SS.top()] < ft[node[i]]) SS.pop();
// cout << node[i] << ' ' << SS.top() << '\n';
g[SS.top()].pb({node[i], h[node[i]] - h[SS.top()]});
g[node[i]].pb({SS.top(), h[node[i]] - h[SS.top()]});
SS.push(node[i]);
}
ll ans = INF;
DJ(Y, node);
for (auto u:node){
if (mark[u] == 1) ans = min(ans, dis[u]);
if (mark[u] == 1 && mark2[u] == 1) ans = 0;
mark[u] = mark2[u] = 0;
g[u].clear();
g[u].shrink_to_fit();
}
return ans;
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
vi A, B, D;
for (int i = 0; i < n - 1; i++){
int x, y, z;
cin >> x >> y >> z;
A.pb(x), B.pb(y), D.pb(z);
}
Init(n, A, B, D);
for (int i = 1; i <= q; i++){
int S, T;
cin >> S >> T;
vi X, Y;
for (int j = 0; j < S; j++){
int x;
cin >> x;
X.pb(x);
}
for (int j = 0; j < T; j++){
int x;
cin >> x;
Y.pb(x);
}
cout << Query(S, X, T, Y) << '\n';
}
return 0;
}
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
*/