| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1270508 | nerrrmin | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 5e5 + 10;
vector < pair < int, int > > g[maxn];
int n, sub[maxn], blocked[maxn];
int all, half;
void calc(int beg, int from)
{
sub[beg] = 1;
for (auto &[nb, dist]: g[beg])
{
if(nb == from)continue;
if(blocked[nb])continue;
sub[beg] += sub[nb];
}
}
int find_centroid(int beg, int from)
{
for (auto [nb, cost]: g[beg])
{
if(nb == from || blocked[nb])continue;
if(sub[nb] > half)return find_centroid(nb, beg);
}
return beg;
}
int root, par[maxn];
int decompose(int v, int from)
{
calc(v, -1);
all = sub[v];
half = all/2;
int nc = find_centroid(v, -1);
par[nc] = from;
blocked[nc] = 1;
for (auto &[nb, w]: g[nc])
{
if(blocked[nb])continue;
int t = decompose(nb, nc);
}
return nc;
}
int dep[maxn], p[maxn], pw[maxn];
int a[maxn * 3], da[maxn * 3], tmr, label[maxn];
int lg[maxn * 3], st[maxn * 3][20];
long long dp[maxn * 3];
void dfs2(int beg, int from, int d, int up)
{
dep[beg] = d;
tmr ++;
a[tmr] = beg;
da[tmr] = d;
label[beg] = tmr;
dp[beg] = up;
for (auto &[nb, cost]: g[beg])
{
if(nb == from)continue;
pw[nb] = cost;
p[nb] = beg;
dfs2(nb, beg, d+1, up + cost);
tmr ++;
a[tmr] = beg;
da[tmr] = d;
}
}
int lca(int from, int to)
{
int l = label[from], r = label[to];
if(l > r)swap(l, r);
int sz = r - l + 1;
int lgche= lg[sz];
int fh = st[l][lgche];
int sh = st[r-(1 << lgche) + 1][lgche];
if(da[fh] < da[sh])return a[fh];
else return a[sh];
}
int dist(int u, int v)
{
int anc = lca(u, v);
return dp[u] + dp[v] - 2 * dp[anc];
}
long long best[maxn]; /// fix to ll
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (int i = 0; i < n-1; ++ i)
{
int from = A[i], to = B[i], w = D[i];
from ++;
to ++;
g[from].pb({to, w});
g[to].pb({from, w});
}
root = decompose(1, -1);
for (int i = 0; i <= n; ++ i)
best[i] = 1e17;
dfs2(1, 0, 0, 0);
int step = 0, val = 1;
for (int i = 0; i <= tmr; ++ i)
{
if(val * 2<= i)
{
step ++;
val *= 2;
}
lg[i] = step;
}
for (int i = 1; i <= tmr; ++ i)
st[i][0] = i;
for (int bit = 1; bit < 20; ++ bit)
{
for (int i = 1; i + (1 << bit) - 1 <= tmr; ++ i)
{
int fh = st[i][bit-1];
int sh = st[i + (1 << (bit - 1))][bit-1];
if(da[fh] < da[sh])st[i][bit] = fh;
else st[i][bit] = sh;
}
}
}
long long Query(int S, int X[], int T, int Y[])
{
int s, t;
s = S;
t = T;
/// update
for (int i = 0; i < s; ++ i)
{
X[i] ++;
int ver = X[i];
while(ver != par[root])
{
best[ver] = min(best[ver], dist(ver, X[i]));
ver = par[ver];
}
}
long long ans = 1e17;
for (int i = 0; i < t; ++ i)
{
Y[i] ++;
int ver = Y[i];
int cnt = 0;
while(ver != par[root])
{
cnt ++;
assert(cnt < n);
ans = min(ans, best[ver] + dist(ver, Y[i]));
ver = par[ver];
}
}
/// kak shte go mahna posle
for (int i = 0; i < s; ++ i)
{
int ver = X[i];
while(ver != par[root])
{
best[ver] = 1e17;
ver = par[ver];
}
}
return ans;
}