| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 467064 | Namnamseo | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
using pp=pair<int,int>;
using ll=long long;
const int maxn = int(5e5) + 10;
const ll inf = (1ll<<60);
int n, q;
vector<pp> e[maxn];
int tin[maxn], tout[maxn], nt;
int par[20][maxn];
int dep[maxn];
ll dd[maxn];
void dfs(int x) {
tin[x] = ++nt;
for (auto tmp:e[x]) {
int y, d; tie(y, d) = tmp;
if (y == par[0][x]) continue;
par[0][y] = x;
dep[y] = dep[x]+1;
dd[y] = dd[x] + d;
dfs(y);
}
tout[x] = nt;
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
for (int df=dep[b]-dep[a], i=18; 0<=i; --i)
if (1&(df>>i)) b = par[i][b];
if (a == b) return a;
for (int i=18; 0<=i; --i) if (par[i][a] != par[i][b])
a = par[i][a], b = par[i][b];
return par[0][a];
}
vector<int> vx, vy;
vector<int> va;
bitset<maxn> isx;
bitset<maxn> isy;
vector<pair<int,ll>> te[maxn];
ll dx[maxn], dy[maxn];
pair<ll,ll> tdfs(int x, pair<ll,ll> pd) {
if (isx[x]) pd.first = 0;
else if (isy[x]) pd.second = 0;
ll cx = inf, cy = inf;
for (auto tmp : te[x]) {
int y; ll d; tie(y, d) = tmp;
ll ccx, ccy; tie(ccx, ccy) = tdfs(y, {pd.first+d, pd.second+d});
cx = min(cx, ccx+d);
cy = min(cy, ccy+d);
}
dx[x] = min(cx, pd.first);
dy[x] = min(cy, pd.second);
if (isx[x]) cx = 0;
else if (isy[x]) cy = 0;
return {cx, cy};
}
int main() { cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i=1; i<n; ++i) {
int a, b, d; cin >> a >> b >> d; ++a; ++b;
e[a].emplace_back(b, d);
e[b].emplace_back(a, d);
}
dfs(1);
for (int i=1; i<=18; ++i) for (int j=1; j<=n; ++j) {
par[i][j] = par[i-1][par[i-1][j]];
}
for(;q--;) {
int nx, ny; cin >> nx >> ny;
vx.resize(nx); vy.resize(ny);
for (int &x : vx) cin >> x, ++x;
for (int &y : vy) cin >> y, ++y;
va.resize(nx + ny);
copy(vx.begin(), vx.end(), va.begin());
copy(vy.begin(), vy.end(), va.begin()+nx);
sort(va.begin(), va.end(), [&](const int& a, const int& b) {
return tin[a] < tin[b];
});
for (int i=0; i+1<nx+ny; ++i) {
int a = va[i], b = va[i+1], l = lca(a, b);
if (l != a && l != b) va.push_back(l);
}
sort(va.begin(), va.end(), [&](const int& a, const int& b) {
return tin[a] < tin[b];
});
va.erase(unique(va.begin(), va.end()), va.end());
static vector<int> stk; stk.clear();
for (int x : va) {
while (!stk.empty()) {
int p = stk.back();
if (tin[p] <= tin[x] && tin[x] <= tout[p]) break;
stk.pop_back();
}
if (!stk.empty()) {
int p = stk.back();
te[p].emplace_back(x, dd[x]-dd[p]);
}
stk.push_back(x);
}
for (int x : vx) isx.set(x);
for (int y : vy) isy.set(y);
tdfs(va[0], {inf, inf});
ll ans = inf;
for (int a : va) ans = min(ans, dx[a]+dy[a]);
cout << ans << '\n';
for (int x : va) te[x].clear();
for (int x : vx) isx.reset(x);
for (int y : vy) isy.reset(y);
}
return 0;
}