| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1274265 | nanaseyuzuki | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "factories.h"
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mn = 5e5 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e9, base = 311;
int n, q, s, t, sz[mn], on[mn], par[mn], d[mn], dist[mn], h[mn], lowest[mn], st[mn], ft[mn], lg2[mn], timer = 0;
pii up[mn][21];
vector <pii> a[mn];
void txl(int u, int p){
st[u] = ft[u] = ++ timer;
up[timer][0] = {h[u], u};
for(auto [v, w] : a[u]){
if(v == p) continue;
h[v] = h[u] + 1;
dist[v] = dist[u] + w;
txl(v, u);
ft[u] = ++ timer;
up[timer][0] = {h[u], u};
}
}
void build(){
for(int k = 1; k <= 20; k++){
for(int i = 1; i + (1 << k) - 1 <= timer; i++){
up[i][k] = min(up[i][k - 1], up[i + (1 << (k - 1))][k - 1]);
}
}
for(int i = 2; i <= timer; i++) lg2[i] = lg2[i / 2] + 1;
}
void pre_dfs(int u, int p){
sz[u] = 1;
for(auto [v, w] : a[u]){
if(on[v] || v == p) continue;
pre_dfs(v, u);
sz[u] += sz[v];
}
}
int get_centroid(int u, int p, int Reina){
for(auto [v, w] : a[u]){
if(on[v] || v == p) continue;
if(2 * sz[v] >= Reina) return get_centroid(v, u, Reina);
}
return u;
}
void dfs(int u, int p){
pre_dfs(u, 0);
u = get_centroid(u, 0, sz[u]);
par[u] = p, on[u] = 1;
d[u] = d[p] + 1;
for(auto [v, w] : a[u]){
if(on[v]) continue;
dfs(v, u);
}
}
int lca(int u, int v){
if(st[u] > st[v]) swap(u, v);
u = st[u], v = ft[v];
int i = lg2[v - u + 1];
return min(up[u][i], up[v - (1 << i) + 1][i]).se;
}
int kc(int u, int v){
int p = lca(u, v);
return dist[u] + dist[v] - 2 * dist[p];
}
void update(int u){
int p = u;
while(p){
lowest[p] = min(lowest[p], kc(u, p));
p = par[p];
}
}
int get(int u){
int p = u, res = inf;
while(p){
res = min(res, kc(u, p) + lowest[p]);
p = par[p];
}
return res;
}
void rollback(int u){
int p = u;
while(p){
lowest[p] = inf, p = par[p];
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++){
int u = A[i], v = B[i], w = D[i];
++ u, ++ v;
a[u].push_back({v, w});
a[v].push_back({u, w});
}
txl(1, 0);
build();
dfs(1, 0);
for(int i = 1; i <= n; i++) lowest[i] = inf;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i++){
++ X[i];
int x = X[i], update(x);
}
int res = inf;
for(int i = 0; i < T; i++){
++ Y[i];
res = min(res, get(Y[i]));
}
for(int i = 0; i < S; i++) rollback(X[i]);
return res;
}