#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define task ""
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const long long INF = 1e18 + 7;
const int MAX = 500005;
int n, q;
int timer;
int h[MAX];
int fr[MAX];
int to[MAX];
int co[MAX];
int sz[MAX];
int tin[MAX];
int par[MAX];
bool rem[MAX];
long long dep[MAX];
long long dist[MAX];
int dp[20][MAX << 1];
vector<int> adj[MAX];
#define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
void dfs(int u, int p) {
dp[0][timer] = u;
tin[u] = timer++;
for (int &id: adj[u]) {
int v = fr[id] ^ to[id] ^ u;
if (v != p && rem[v] == 0) {
dep[v] = dep[u] + co[id];
h[v] = h[u] + 1;
dfs(v, u);
dp[0][timer++] = u;
}
}
}
int LCA(int u, int v) {
int l = tin[u], r = tin[v]; if (l > r) swap(l, r);
int k = 31 - __builtin_clz(r - l + 1);
return COMBINE(dp[k][l], dp[k][r - (1 << k) + 1]);
}
long long DIST(int u, int v) {
return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}
int dfsSZ(int u, int p) {
sz[u] = 1;
for (int &id: adj[u]) {
int v = fr[id] ^ to[id] ^ u;
if (v != p && rem[v] == 0) {
sz[u] += dfsSZ(v, u);
}
}
return sz[u];
}
int findCentroid(int u, int p, int n) {
for (int &id: adj[u]) {
int v = fr[id] ^ to[id] ^ u;
if (v != p && rem[v] == 0) {
if ((sz[v] << 1) > n)
return findCentroid(v, u, n);
}
}
return u;
}
void solve(int u, int p) {
int c = findCentroid(u, p, dfsSZ(u, p));
dist[c] = INF;
rem[c] = true;
par[c] = p;
for (int &id: adj[c]) {
int v = fr[id] ^ to[id] ^ u;
if (v != p && rem[v] == 0) {
solve(v, c);
}
}
}
void Init(int _n, int _a[], int _b[], int _d[]) {
n = _n;
for (int i = 0; i < n - 1; ++i) {
fr[i] = _a[i];
to[i] = _b[i];
co[i] = _d[i];
adj[fr[i]].push_back(i);
adj[to[i]].push_back(i);
}
dfs(0, -1);
for (int j = 1; (1 << j) <= timer; ++j) {
for (int i = 0; i + (1 << j) - 1 <= timer - 1; ++i)
dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
}
solve(0, -1);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; ++i) {
for (int cur = X[i]; cur != -1; cur = par[cur])
dist[cur] = min(dist[cur], DIST(X[i], cur));
}
long long res = INF;
for (int i = 0; i < T; ++i) {
for (int cur = Y[i]; cur != -1; cur = par[cur])
res = min(res, dist[cur] + DIST(Y[i], cur));
}
for (int i = 0; i < S; ++i) {
for (int cur = X[i]; cur != -1; cur = par[cur])
dist[cur] = INF;
}
return res;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:97:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
97 | dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
| ~~^~~
factories.cpp:24:37: note: in definition of macro 'COMBINE'
24 | #define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
| ^
factories.cpp:97:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
97 | dp[j][i] = COMBINE(dp[j - 1][i], dp[j - 1][i + (1 << j - 1)]);
| ~~^~~
factories.cpp:24:50: note: in definition of macro 'COMBINE'
24 | #define COMBINE(u, v) (h[(u)] <= h[(v)] ? (u) : (v))
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
62288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
62044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
62288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
