| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 879092 | serifefedartar | 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>
#include "factories.h"
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 5e5 + 100;
vector<vector<pair<int,int>>> graph;
int marked[MAXN], sz[MAXN], up[LOGN][MAXN], depth[MAXN];
int par[MAXN];
ll depth_dist[MAXN], ans[MAXN];
int get_sz(int node, int parent) {
sz[node] = 1;
for (auto u : graph[node]) {
if (u.f == parent || marked[u.f])
continue;
sz[node] += get_sz(u.f, node);
}
return sz[node];
}
int find_centro(int node, int parent, int n) {
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f] && sz[u.f] * 2 > sz[node])
return find_centro(u.f, node, n);
}
return node;
}
void decompose(int node, bool q) {
int n = get_sz(node, node);
int centro = find_centro(node, node, n);
marked[centro] = true;
if (q)
par[centro] = -1;
else
par[centro] = node;
for (auto u : graph[centro]) {
if (u.f != parent && !marked[u.f])
decompose(u.f, false);
}
}
void dfs(int node, int parent) {
for (auto u : graph[node]) {
if (u.f == parent)
continue;
depth[u.f] = depth[node] + 1;
depth_dist[u.f] = depth_dist[node] + u.s;
up[0][u.f] = node;
for (int i = 1; i < LOGN; i++)
up[i][u.f] = up[i-1][up[i-1][u.f]];
dfs(u.f, node);
}
}
int find(int node, int k) {
for (int i = 0; i < LOGN; i++) {
if ((1<<i) & k)
node = up[i][node];
}
return node;
}
int lca(int a, int b) {
if (depth[b] > depth[a])
swap(a, b);
a = find(a, depth[a] - depth[b]);
if (a == b)
return a;
for (int i = LOGN - 1; i >= 0; i--) {
if (up[i][a] != up[i][b]) {
a = up[i][a];
b = up[i][b];
}
}
return up[0][a];
}
int dist(int a, int b) {
return depth_dist[a] + depth_dist[b] - 2 * depth_dist[lca(a, b)];
}
void Init(int N, vector<int> A, vector<int> B, vector<int> D) {
graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
for (int i = 0; i < N-1; i++) {
graph[A[i]].push_back({B[i], D[i]});
graph[B[i]].push_back({A[i], D[i]});
}
dfs(1, 1);
decompose(1, true);
for (int i = 0; i < MAXN; i++)
ans[i] = 1e15;
}
void add(int node) {
int now = node;
while (now != -1) {
ans[now] = min(ans[now], dist(now, node));
now = par[now];
}
}
void remove(int node) {
while (node != -1) {
ans[node] = 1e15;
node = par[node];
}
}
ll qry(int node) {
int now = node;
ll res = 1e15;
while (now != -1) {
res = min(res, dist(now, node) + ans[now]);
now = par[now];
}
return res;
}
ll Query(int S, vector<int> X, int T, vector<int> Y) {
for (auto u : X)
add(u);
ll mn = 1e16;
for (auto u : Y)
mn = min(mn, qry(u));
for (auto u : X)
remove(u);
return mn;
}