| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1126385 | whoknow | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 500005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18;
int n, ntest;
vector<ii>g[MAXN];
int timedfs, Q;
ll best[MAXN], dist[MAXN];
bool A[MAXN], B[MAXN], del[MAXN];
int timed[MAXN], range[MAXN], sz[MAXN], par[MAXN], h[MAXN];
int f[2 * MAXN][20];
int minimize(int x, int y)
{
if(h[x] < h[y])
return x;
return y;
}
int log2(int x)
{
return 31 - __builtin_clz(x);
}
void build(int u, int p)
{
h[u] = h[p] + 1;
f[++timedfs][0] = u;
range[u] = timedfs;
for(ii v : g[u])
{
if(v.F == p)
continue;
dist[v.F] = dist[u] + v.S;
build(v.F, u);
f[++timedfs][0] = u;
}
}
void RMQ()
{
for(int j = 1; j <= log2(timedfs); j++)
for(int i = 1; i <= timedfs - (1 << j) + 1; i++)
f[i][j] = minimize(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int lca(int u, int v)
{
int l = range[u], r = range[v];
if(l > r)
swap(l, r);
int k = log2(r - l + 1);
return minimize(f[l][k], f[r - (1 << k) + 1][k]);
}
int get_size(int u, int p)
{
int cnt = 1;
for(ii v : g[u])
if(v.F != p && !del[v.F])
cnt += get_size(v.F, u);
return sz[u] = cnt;
}
int get_centroid(int u, int p, int size)
{
for(ii v : g[u])
if(v.F != p && !del[v.F] && sz[v.F] > size / 2)
return get_centroid(v.F, u, size);
return u;
}
void dfs(int u, int p)
{
u = get_centroid(u, 0, get_size(u, 0));
del[u] = 1;
par[u] = p;
for(ii v : g[u])
if(!del[v.F])
dfs(v.F, u);
}
void update(int u)
{
int v = u;
while(u != 0)
{
if(timed[u] != Q)
best[u] = dist[u] + dist[v] - 2LL * dist[lca(v, u)], timed[u] = Q;
else
best[u] = min(best[u], dist[u] + dist[v] - 2LL * dist[lca(v, u)]);
u = par[u];
}
}
ll get(int u)
{
int v = u;
ll ans = INF;
while(u != 0)
{
if(timed[u] == Q)
ans = min(ans, dist[u] + dist[v] - 2LL * dist[lca(u, v)]+best[u]);
u = par[u];
}
return ans;
}
void INIT(int N,int A[],int B[],int D[])
{
for(int i=1;i<N;i++)
{
A[i]++,B[i]++;
g[A[i]].push_back({B[i],D[i]});
g[B[i]].push_back({A[i],D[i]});
}
build(1, 0);
RMQ();
dfs(1, 0);
}
ll QUERY(int S,int T,int X[],int Y[])
{
Q++;
ll res=INF;
for(int i=1;i<=S;i++)
{
X[i]++;
update(X[i]);
}
for(int i=1;i<=T;i++)
{
Y[i]++;
res=min(res,get(Y[i]));
}
return res;
}