| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 921585 | vjudge1 | 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 int long long
#define endl '\n'
#define F first
#define S second
const int N = 1e5 + 7, inf = 1e18, LOG = 19, SEG = 1e6;
int st[N], fn[N], dis[N], par[LOG][N], t = -1, n, seg[SEG][2], h[N], ans;
vector<pair<int, int>> adj[N];
void dfs(int v, int p, int d1, int h1) {
dis[v] = d1;
h[v] = h1;
st[v] = ++t;
par[0][v] = p;
for (int i = 1; i < LOG; i++)
par[i][v] = par[i - 1][par[i - 1][v]];
for (auto u : adj[v])
if (u.first != p)
dfs(u.first, v, d1 + u.second, h1 + 1);
fn[v] = t;
return;
}
int getp(int v, int k) {
for (int i = LOG - 1; ~i; i--)
if ((k >> i) & 1)
v = par[i][v];
return v;
}
int lca(int v, int u) {
if (h[v] < h[u])
swap(v, u);
v = getp(v, h[v] - h[u]);
if (v == u)
return v;
for (int i = LOG - 1; ~i; i--)
if (par[i][v] != par[i][u]) {
v = par[i][v];
u = par[i][u];
}
return par[0][v];
}
void update(int v, int l, int r, int i, int k, bool g) {
// cout << v << "A" << endl;
if (l == r) {
seg[v][g] = k;
return;
}
int mid = (r + l) >> 1;
(i <= mid) ? update(v << 1, l, mid, i, k, g) : update((v << 1) | 1, mid + 1, r, i, k, g);
seg[v][g] = min(seg[v << 1][g], seg[(v << 1) | 1][g]);
}
int get(int v, int l, int r, int ql, int qr, bool g) {
// cout << "a" << seg[v][g] << " " << l << " " << r << " " << ql << " " << qr << endl;
if (ql <= l && r <= qr)
return seg[v][g];
if (r < ql || qr < l)
return inf;
int mid = (r + l) >> 1;
return min(get(v << 1, l, mid, ql, qr, g), get((v << 1) | 1, mid + 1, r, ql, qr, g));
}
void rem(int v, int l, int r, int i, bool g) {
// cout << v << "C" << endl;
seg[v][g] = inf;
if (l == r)
return;
int mid = (r + l) >> 1;
(i <= mid) ? rem(v << 1, l, mid, i, g) : rem((v << 1) | 1, mid + 1, r, i, g);
}
void Init(int N, int A[], int B[], int D[]) {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0, 0, 0);
queue<pair<int, pair<int, int>>> q;
q.push({1, {0, n - 1}});
while (q.size()) {
int v = q.front().first, l = q.front().second.first, r = q.front().second.second;
seg[v][0] = seg[v][1] = inf;
q.pop();
// cout << v << endl;
if (l != r) {
int mid = (l + r) >> 1;
q.push({v << 1, {l, mid}});
q.push({(v << 1) | 1, {mid + 1, r}});
}
}
}
long long Query(int S, int X[], int T, int Y[]) {
vector<pair<int, int>> sv;
for (int i = 0; i < S; i++) {
update(1, 0, n - 1, st[X[i]], dis[X[i]], 0);
sv.push_back({st[X[i]], X[i]});
}
for (int i = 0; i < T; i++) {
update(1, 0, n - 1, st[Y[i]], dis[Y[i]], 1);
sv.push_back({st[Y[i]], Y[i]});
}
sort(sv.begin(), sv.end());
ans = inf;
for (int i = 0; i < int32_t(sv.size()); i++) {
int v = sv[i].second;
int f = get(1, 0, n - 1, st[v], fn[v], 0) + get(1, 0, n - 1, st[v], fn[v], 1) - (2 * dis[v]);
// cout << f << endl;
// cout << get(1, 0, n - 1, st[v], fn[v], 0) << " " << get(1, 0, n - 1, st[v], fn[v], 1) << endl;
ans = min(ans, f);
if (i < int32_t(sv.size()) - 1) {
v = lca(sv[i].second, sv[i + 1].second);
f = get(1, 0, n - 1, st[v], fn[v], 0) + get(1, 0, n - 1, st[v], fn[v], 1) - (2 * dis[v]);
ans = min(ans, f);
// cout << f << endl;
// cout << get(1, 0, n - 1, st[v], fn[v], 0) << " " << get(1, 0, n - 1, st[v], fn[v], 1) << endl;
// cout << v<< endl;
}
}
for (int i = 0; i < S; i++)
rem(1, 0, n - 1, st[X[i]], 0);
for (int i = 0; i < T; i++)
rem(1, 0, n - 1, st[Y[i]], 1);
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int V[6] = {0, 1, 2, 2, 4, 1}, U[6] = {1, 2, 3, 4, 5, 6}, DIsecond[6] = {4, 4, 5, 6, 5, 3};
Init(7, V, U, DIsecond);
int A[2] = {0, 6}, B[2] = {3, 4};
cout << Query(2, A, 2, B) << endl;
int AA[3] = {0, 1, 3}, BB[2] = {4, 6};
cout << Query(3, AA, 2, BB) << endl;
int AAA[1] = {2}, BBB[1] = {5};
cout << Query(1, AAA, 1, BBB);
}*/