| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 531805 | hgmhc | 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>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define PER(i,a,b) for (auto i = (b); i >= (a); --i)
#define log2(x) (31-__builtin_clz(x))
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define el '\n'
using namespace std; using ll = long long;
void solution(); int main() {ios::sync_with_stdio(0); cin.tie(0); solution();}
const int N = 500003;
int n, q; vector<pair<int,ll>> adj[N];
//**-------- WARNING! 0-index to 1-index --------**//
int par[N], lev[N], spt[N][log2(N)+1];
ll dist[5003][5003], depth[N];
void precom1(int r, int s, int e = 0) {
for (auto [u,w] : adj[s]) if (u != e) {
dist[r][u] = dist[r][s]+w;
precom1(r,u,s);
}
}
void precom2(int s = 1, int e = 0) {
for (auto [u,w] : adj[s]) if (u != e) {
depth[u] = depth[s]+w;
par[u] = s;
lev[u] = lev[s]+1;
precom2(u,s);
}
}
void input() {
cin >> n >> q;
REP(i,0,n-2) {
int a, b, d;
cin >> a >> b >> d;
adj[a+1].push_back({b+1,d}); adj[b+1].push_back({a+1,d});
}
}
void solution() {
input();
if (n <= 5000 && q <= 5000) {
REP(i,1,n) precom1(i,i);
while (q--) {
int s, t; cin >> s >> t; vector<int> X(s), Y(t);
for (int& x : X) {cin >> x; ++x;}
for (int& y : Y) {cin >> y; ++y;}
ll ans = LLONG_MAX;
for (int x : X) for (int y : Y)
mup(ans,dist[x][y]);
cout << ans << el;
}
} else {
precom2();
//make sparse table
REP(j,1,n) spt[j][0] = par[j];
REP(i,1,log2(N)) REP(j,1,n) spt[j][i] = spt[spt[j][i-1]][i-1];
function<int(int,int)> lca = [&](int a, int b) {
if (lev[a] > lev[b]) swap(a,b);
REP(i,0,log2(N)) if ((lev[b]-lev[a])&(1<<i))
b = spt[b][i];
if (a == b) return a;
PER(x,0,log2(N))
if (spt[a][x] != spt[b][x])
a = spt[a][x], b = spt[b][x];
return spt[a][0];
};
while (q--) {
int s, t; cin >> s >> t; vector<int> X(s), Y(t);
for (int& x : X) {cin >> x; ++x;} for (int& y : Y) {cin >> y; ++y;}
ll ans = LLONG_MAX;
for (int x : X) for (int y : Y) mup(ans,depth[x]+depth[y]-2*depth[lca(x,y)]);
cout << ans << el;
}
}
//Consider ∑S, ∑T <= 10^6
}