| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 532359 | mmonteiro | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#include "factories.h"
#define int long long
const int MAX = 6e5;
const int OO = 0x3f3f3f3f3f3f3f3f;
#define ii pair<int, int>
#define f first
#define s second
int n, max_log;
vector<ii> G[MAX];
int anc[MAX][22], depth[MAX];
int ans[MAX], weight[MAX];
int CD[MAX], sz[MAX];
bool cut[MAX];
void dfs(int v, int p, int d)
{
anc[v][0] = p;
depth[v] = d;
if(d) max_log = max(max_log, (int)log2(d));
for(auto [u, w] : G[v]) {
if(u != p) {
weight[u] = weight[v] + w;
dfs(u, v, d + 1);
}
}
}
void build()
{
memset(anc, -1, sizeof(anc));
dfs(0, -1, 0);
for(int j = 1; j <= max_log; j++)
for(int i = 0; i < n; i++)
if(anc[i][j-1] != -1)
anc[i][j] = anc[anc[i][j-1]][j-1];
}
int walk(int v, int k)
{
while(k)
v = anc[v][(int)(log2(k & -k))], k -= (k&-k);
return v;
}
int lca(int u, int v)
{
if(depth[u] > depth[v]) u = walk(u, depth[u] - depth[v]);
if(depth[u] < depth[v]) v = walk(v, depth[v] - depth[u]);
if(u == v) return u;
for(int i = max_log; i >= 0; i--)
if(anc[u][i] != anc[v][i])
{
u = anc[u][i];
v = anc[v][i];
}
return anc[u][0];
}
int dfs2(int v, int p)
{
int s = 1;
for(auto [u, w] : G[v])
if(!cut[u] and u != p)
s += dfs2(u, v);
return sz[v] = s;
}
int find_centroid(int v, int p, int tot)
{
int next, cnt = 0;
for(auto [u, w] : G[v])
if(!cut[u] and u != p and sz[u] > cnt)
cnt = sz[u], next = u;
if(cnt > tot / 2) return find_centroid(next, v, tot);
return v;
}
void build_centroid_tree(int v, int p)
{
dfs2(v, -1);
int u = find_centroid(v, -1, sz[v]);
CD[u] = p;
cut[u] = true;
for(auto [w, h] : G[u])
if(!cut[w])
build_centroid_tree(w, u);
}
int dist(int u, int v)
{
return weight[u] + weight[v] - 2*weight[lca(u, v)];
}
void paint(int v, int u)
{
if(v == -1) return;
ans[v] = min(ans[v], dist(v, u));
paint(CD[v], u);
}
void unpaint(int v, int u)
{
if(v == -1) return;
ans[v] = OO;
paint(CD[v], u);
}
int query(int v, int u, int d)
{
if(v == -1)
return d;
return query(CD[v], u, min(d, dist(v, u) + ans[v]));
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n-1; i++) {
G[ A[i] ].push_back({B[i], D[i]});
G[ B[i] ].push_back({A[i], D[i]});
}
build();
build_centroid_tree(0, -1);
memset(ans, 63, sizeof(ans));
}
long long Query(int S, int X[], int T, int Y[]) {
for(int j = 0; j < S; ++j)
paint(X[j], X[j]);
int rep = OO;
for(int j = 0; j < T; ++j) {
rep = min(rep, query(Y[j], Y[j], OO));
}
for(int j = 0; j < S; ++j)
unpaint(X[j], X[j]);
return rep;
}