| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1134107 | Nelt | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 5e5 + 5, lg = 20;
vector<pair<ll, ll>> g[N];
ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
bool used[N];
void dfs(ll v, ll par = 0)
{
up[0][v] = par;
for (ll i = 1; i < lg; i++) up[i][v] = up[i - 1][up[i - 1][v]];
for (auto [to, w] : g[v])
if (to != par) depth[to] = depth[v] + 1, dis[to] = dis[v] + w, dfs(to, v);
}
ll lca(ll a, ll b)
{
if (depth[a] < depth[b]) swap(a, b);
for (ll bit = lg - 1; bit >= 0; bit--) if (depth[a] - (1 << bit) >= depth[b]) a = up[bit][a];
if (a == b) return a;
for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
return up[0][a];
}
ll dist(ll a, ll b)
{
return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}
void init(ll v, ll par = -1)
{
sub[v] = 1;
for (auto [to, w] : g[v])
if (to != par and !used[to]) init(to, v), sub[v] += sub[to];
}
ll findcentroid(ll v, ll par = -1, ll sz = 0)
{
for (auto [to, w] : g[v])
if (to != par and !used[to] and sub[to] > sz / 2) return findcentroid(to, v, sz);
return v;
}
ll decompose(ll v)
{
init(v);
ll cent = findcentroid(v, -1, sub[v]);
used[cent] = 1;
for (auto [to, w] : g[cent])
if (!used[to])
p[decompose(to)] = cent;
return cent;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (ll i = 0; i < n - 1; i++) g[A[i]].push_back(make_pair(B[i], D[i])), g[B[i]].push_back(make_pair(A[i], D[i]));
dfs(0);
for (ll i = 0; i < n; i++) best[i] = 1e18, p[i] = -1;
decompose(0);
}
long long Query(int S, int X[], int T, int Y[])
{
for (ll i = 0; i < S; i++)
{
ll v = X[i];
while (v >= 0)
{
best[v] = min(best[v], dist(v, X[i]));
v = p[v];
}
}
ll ans = 9e18;
for (ll i = 0; i < T; i++)
{
ll v = Y[i];
while (v >= 0)
{
ans = min(ans, best[v] + dist(v, Y[i]));
v = p[v];
}
}
for (ll i = 0; i < S; i++)
{
ll v = X[i];
while (v >= 0)
{
best[v] = 1e18;
v = p[v];
}
}
return ans;
}
#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 5e5 + 5, lg = 20;
vector<pair<ll, ll>> g[N];
ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
bool used[N];
void dfs(ll v, ll par = 0)
{
up[0][v] = par;
for (ll i = 1; i < lg; i++) up[i][v] = up[i - 1][up[i - 1][v]];
for (auto [to, w] : g[v])
if (to != par) depth[to] = depth[v] + 1, dis[to] = dis[v] + w, dfs(to, v);
}
ll lca(ll a, ll b)
{
if (depth[a] < depth[b]) swap(a, b);
for (ll bit = lg - 1; bit >= 0; bit--) if (depth[a] - (1 << bit) >= depth[b]) a = up[bit][a];
if (a == b) return a;
for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
return up[0][a];
}
ll dist(ll a, ll b)
{
return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}
void init(ll v, ll par = -1)
{
sub[v] = 1;
for (auto [to, w] : g[v])
if (to != par and !used[to]) init(to, v), sub[v] += sub[to];
}
ll findcentroid(ll v, ll par = -1, ll sz = 0)
{
for (auto [to, w] : g[v])
if (to != par and !used[to] and sub[to] > sz / 2) return findcentroid(to, v, sz);
return v;
}
ll decompose(ll v)
{
init(v);
ll cent = findcentroid(v, -1, sub[v]);
used[cent] = 1;
for (auto [to, w] : g[cent])
if (!used[to])
p[decompose(to)] = cent;
return cent;
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (ll i = 0; i < n - 1; i++) g[A[i]].push_back(make_pair(B[i], D[i])), g[B[i]].push_back(make_pair(A[i], D[i]));
dfs(0);
for (ll i = 0; i < n; i++) best[i] = 1e18, p[i] = -1;
decompose(0);
}
long long Query(int S, int X[], int T, int Y[])
{
for (ll i = 0; i < S; i++)
{
ll v = X[i];
while (v >= 0)
{
best[v] = min(best[v], dist(v, X[i]));
v = p[v];
}
}
ll ans = 9e18;
for (ll i = 0; i < T; i++)
{
ll v = Y[i];
while (v >= 0)
{
ans = min(ans, best[v] + dist(v, Y[i]));
v = p[v];
}
}
for (ll i = 0; i < S; i++)
{
ll v = X[i];
while (v >= 0)
{
best[v] = 1e18;
v = p[v];
}
}
return ans;
}