/* In the name of Allah */
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18 + 5;
const int N = 5e5 + 5, LG = 18 + 2;
int n, q, h[N], st[N], en[N], par[N][LG];
vector<pair<int, int>> adj[N];
int n1, n2, u1[N], u2[N];
long long dist[N];
struct Segment {
long long seg[N << 2];
Segment() {
memset(seg, 63, sizeof seg);
}
void update(int p, long long x, int id = 1, int st = 0, int en = n) {
if (en - st == 1) {
seg[id] = x;
return;
}
int mid = st + en >> 1;
if (p < mid)
update(p, x, id << 1, st, mid);
else
update(p, x, id << 1 | 1, mid, en);
seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
}
long long get(int l, int r, int id = 1, int st = 0, int en = n) {
if (r <= st || en <= l)
return INF;
if (l <= st && en <= r)
return seg[id];
int mid = st + en >> 1;
return min(get(l, r, id << 1, st, mid), get(l, r, id << 1 | 1, mid, en));
}
void clear(int id = 1, int st = 0, int en = n) {
if (seg[id] >= INF)
return;
seg[id] = INF;
if (en - st == 1)
return;
int mid = st + en >> 1;
clear(id << 1, st, mid);
clear(id << 1 | 1, mid, en);
}
} seg1, seg2;
inline int lca(int u, int v) {
if (h[u] > h[v])
swap(u, v);
for (int i = LG - 1; ~i; i--)
if (h[v] - h[u] >> i & 1)
v = par[v][i];
for (int i = LG - 1; ~i; i--)
if (par[u][i] ^ par[v][i]) {
u = par[u][i];
v = par[v][i];
}
return u ^ v? par[u][0]: u;
}
void dfs(int u) {
static int time = 0;
for (int i = 0; i < LG - 1; i++)
par[u][i + 1] = par[par[u][i]][i];
st[u] = time++;
for (auto v: adj[u])
if (v.first ^ par[u][0]) {
h[v.first] = h[par[v.first][0] = u] + 1;
dist[v.first] = dist[u] + v.second;
dfs(v.first);
}
en[u] = time;
}
inline bool cmp(int u, int v) {
return st[u] < st[v];
}
void Init(int N, int A[], int B[], int D[]) {
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]});
}
n = N, dfs(0);
}
inline long long solve() {
long long ans = INF;
sort(u1, u1 + n1, cmp);
sort(u2, u2 + n2, cmp);
seg1.clear(), seg2.clear();
for (int i = 0; i < n1; i++)
seg1.update(st[u1[i]], dist[u1[i]]);
for (int i = 0; i < n2; i++)
seg2.update(st[u2[i]], dist[u2[i]]);
for (int i = 0, p = 0; i < n1; i++) {
ans = min(ans, seg2.get(st[u1[i]], en[u1[i]]) - dist[u1[i]]);
while (p < n2 && !cmp(u1[i], u2[p]))
p++;
if (p < n2) {
int x = lca(u1[i], u2[p]);
ans = min(ans, dist[u1[i]] + seg2.get(st[x], en[x]) - 2 * dist[x]);
}
}
for (int i = 0, p = 0; i < n2; i++) {
ans = min(ans, seg1.get(st[u2[i]], en[u2[i]]) - dist[u2[i]]);
while (p < n1 && !cmp(u2[i], u1[p]))
p++;
if (p < n1) {
int x = lca(u2[i], u1[p]);
ans = min(ans, dist[u2[i]] + seg1.get(st[x], en[x]) - 2 * dist[x]);
}
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
n1 = S, n2 = T;
copy(X, X + S, u1);
copy(Y, Y + T, u2);
return solve();
}
Compilation message
factories.cpp: In member function 'void Segment::update(int, long long int, int, int, int)':
factories.cpp:23:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = st + en >> 1;
~~~^~~~
factories.cpp: In member function 'long long int Segment::get(int, int, int, int, int)':
factories.cpp:35:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = st + en >> 1;
~~~^~~~
factories.cpp: In member function 'void Segment::clear(int, int, int)':
factories.cpp:44:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = st + en >> 1;
~~~^~~~
factories.cpp: In function 'int lca(int, int)':
factories.cpp:54:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
if (h[v] - h[u] >> i & 1)
~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
43768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
43640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
43768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
