| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 888898 | canhnam357 | 공장들 (JOI14_factories) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#define int long long
#define MASK(i) (1LL << (i))
using namespace std;
const long long inf = 1e18;
const int N = 5e5 + 5;
// 1-indexed Centroid Decomposition
//int __lg(int n) { return log2(n) + 0.0001; } // Microsoft Visualstudio doesn't have __lg function, this help error not occurrence =))
vector<pair<int, int>> G[N];
int sz[N], par_centroid[N], h[N] = {}, id[N] = {}, par[N][20], del[N] = {};
long long d[N][20], ans[N], dpar[N][20];
int timer;
int dfs(int u, int p) {
sz[u] = 1;
for (auto v : G[u]) if (v.first != p && !del[v.first]) {
sz[u] += dfs(v.first, u);
}
return sz[u];
}
int centroid(int u, int p, int n) {
for (auto v : G[u]) if (v.first != p && !del[v.first]) {
if (sz[v.first] > n / 2) return centroid(v.first, u, n);
}
return u;
}
void build(int u, int p) {
int n = dfs(u, p);
int c = centroid(u, p, n);
par_centroid[c] = p;
del[c] = 1;
for (auto v : G[c]) {
if (!del[v.first])
build(v.first, c);
}
}
void first_dfs(int u, int p) {
for (auto v : G[u]) if (v.first != p) {
h[v.first] = h[u] + 1;
par[v.first][0] = u;
d[v.first][0] = v.second;
first_dfs(v.first, u);
}
}
long long get_dis(int u, int v)
{
long long dis = 0;
if (h[u] > h[v]) swap(u, v);
int k = h[v] - h[u];
int lg = (k == 0 ? -1 : __lg(k));
for (int i = 0; i <= lg; i++) if (k & MASK(i))
{
dis += d[v][i];
v = par[v][i];
}
if (v == u) return dis;
lg = (h[v] == 0 ? -1 : __lg(h[v]));
for (int i = lg; i >= 0; i--)
{
if (par[v][i] != par[u][i])
{
dis += d[v][i] + d[u][i];
v = par[v][i];
u = par[u][i];
}
}
return dis + d[v][0] + d[u][0];
}
void modify(int u) {
for (int v = u, level = 0; v != 0; v = par_centroid[v], level++)
{
if (id[v] == timer)
{
ans[v] = min(ans[v], dpar[u][level]);
}
else
{
id[v] = timer;
ans[v] = dpar[u][level];
}
}
}
long long query(int u) {
long long mn = inf;
for (int v = u, level = 0; v != 0; v = par_centroid[v], level++)
{
if (id[v] == timer)
mn = min(mn, ans[v] + dpar[u][level]);
}
return mn;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
timer = 0;
for (int i = 0; i < n - 1; i++)
{
int u, v, w;
cin >> u >> v >> w;
u++, v++;
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
first_dfs(1, 0); // calculate h, par for lca
// RMQ for lca
{
int lg = __lg(n);
for (int i = 1; i <= lg; i++)
{
for (int j = 1; j <= n; j++)
{
par[j][i] = par[par[j][i - 1]][i - 1];
d[j][i] = d[j][i - 1] + d[par[j][i - 1]][i - 1];
}
}
}
build(1, 0);
for (int i = 1; i <= n; i++)
{
for (int v = i, level = 0; v; v = par_centroid[v], level++)
{
dpar[i][level] = get_dis(i, v);
}
}
// par_centroid[1] = 0
while (q--)
{
timer++;
int s, t;
cin >> s >> t;
for (int i = 0; i < s; i++)
{
int x;
cin >> x;
x++;
modify(x);
}
long long ans = inf;
for (int i = 0; i < t; i++)
{
int x;
cin >> x;
x++;
ans = min(ans, query(x));
}
// cout << "ANSWER ";
cout << ans << '\n';
}
return 0;
}