| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 38055 | MatheusLealV | Factories (JOI14_factories) | C++14 | 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>
#define N 500050
#include "factories.h"
#define logn 20
#define inf 200000000000000000
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, q, nivel[N], block[N], sz[N], tot, pai[N], root, tmp, ini[N];
ll dist[N], ans[N];
vector<pii> grafo[N];
vector<int> tree[N], euler;
pii best;
pii dp[N][logn];
void build_table()
{
for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(nivel[i], euler[i]);
for(int j = 1; j < logn; j++)
{
for(int i = 0; i < euler.size(); i++)
{
if(i + (1<<(j - 1)) < N) dp[i][j] = min(dp[i][j - 1],dp[ i + (1<<(j - 1)) ][j - 1]);
else dp[i][j] = dp[i][j - 1];
}
}
}
int query(int l, int r)
{
if(l == r) return euler[l];
int e = 31-__builtin_clz(r-l);
return min(dp[l][e], dp[r - (1<<e) + 1][e]).s;
}
void initi()
{
for(int i = 0; i < euler.size(); i++) nivel[i] = nivel[euler[i]];
build_table();
}
int lca(int a, int b)
{
return query(min(ini[a], ini[b]), max(ini[a], ini[b]));
}
void dfs(int x, int p)
{
if(ini[x] == -1) ini[x] = tmp;
euler.push_back(x);
tmp ++;
for(int i = 0; i < grafo[x].size(); i++)
{
int v = grafo[x][i].f, peso = grafo[x][i].s;
if(v == p) continue;
nivel[v] = nivel[x] + 1;
dist[v] = dist[x] + (ll)peso;
dfs(v, x);
euler.push_back(x);
tmp ++;
}
}
int tam(int x, int p)
{
sz[x] = 1;
for(int i = 0; i < grafo[x].size(); i++)
{
int v = grafo[x][i].f;
if(v == p || block[v]) continue;
sz[x] += tam(v, x);
}
return sz[x];
}
void split(int x, int p)
{
int maior = tot - sz[x];
for(int i = 0; i < grafo[x].size(); i++)
{
int v = grafo[x][i].f;
if(v == p || block[v]) continue;
split(v, x);
maior = max(maior, sz[v]);
}
if(maior < best.f) best = pii(maior, x);
}
int find_centroid(int x)
{
tot = tam(x, x);
best = pii(2*N, 0);
split(x, x);
return best.s;
}
int decomp(int x)
{
x = find_centroid(x);
block[x] = 1;
for(auto v: grafo[x])
{
if(block[v.f]) continue;
v.f = decomp(v.f);
tree[x].push_back(v.f);
tree[v.f].push_back(x);
}
return x;
}
void dfs2(int x, int p)
{
pai[x] = p;
for(auto v: tree[x])
{
if(v == p) continue;
pai[v] = x;
dfs2(v, x);
}
}
ll distancia(int a, int b)
{
return dist[a] + dist[b] - 2*dist[lca(a, b)];
}
void paint(int x)
{
ans[x] = 0;
int u = x;
while(1)
{
ans[pai[x]] = min(ans[pai[x]], distancia(u, pai[x]));
if(x == pai[x]) return;
x = pai[x];
}
}
void clear(int x)
{
ans[x] = inf;
int u = x;
while(1)
{
ans[pai[x]] = inf;
if(x == pai[x]) return;
x = pai[x];
}
}
ll query(int x)
{
int u = x;
ll resp = inf;
resp = min(resp, ans[x]);
while(1)
{
resp = min(resp, distancia(x, u) + ans[x]);
if(x == pai[x]) return resp;
x = pai[x];
}
}
void Init(int N_, int A[], int B[], int D[])
{
n = N_;
for(int i = 0; i < N; i++) ans[i] = inf;
for(int i = 0; i < n - 1; i++)
{
int a = A[i], b = B[i], c = D[i];
a++, b++;
grafo[a].push_back(pii(b, c));
grafo[b].push_back(pii(a, c));
}
memset(ini, -1, sizeof ini);
dfs(1, 1);
initi();
root = decomp(1);
dfs2(root, root);
}
ll Query(int S, int X[], int T, int Y[])
{
ll ans = inf;
for(int i = 0; i < S ; i++) paint(X[i] + 1);
for(int i = 0; i < T; i++) ans = min(ans, query(Y[i] + 1));
for(int i = 0; i < S; i++) clear(X[i] + 1);
return ans;
}