#include <bits/stdc++.h>
using namespace std;
// keep track of min distance from query i 0 node to ancestor and
// min distance form query i 1 node to ancestor
// for each query, for each node, for each ancestor of node record min distance for this ancestor for this query
// for second list, do same while keeping track of min distance found so far
const int Ni = 1e5+1;
const int S = 17;
vector<pair<int,int>> adj[Ni];
int sz[Ni];
int up[Ni][S];
int dep[Ni];
long long dist[Ni];
bool cen[Ni];
int cp[Ni];
int n;
long long mins[Ni];
void dsz(int u, int p) {
sz[u] = 1;
for(pair<int,int> i : adj[u]) {
if (i.first != p && !cen[i.first]) {
dsz(i.first,u);
sz[u] += sz[i.first];
}
}
}
void dfsa(int u, int p) {
for(int i = 1; i < S; i++) {
up[u][i] = up[up[u][i-1]][i-1];
}
for(pair<int,int> i : adj[u]) {
if (i.first != p) {
dist[i.first] = dist[u]+i.second;
dep[i.first] = dep[up[i.first][0] = u] + 1;
dfsa(i.first,u);
}
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x,y);
x = up[x][dep[x]-dep[y]];
if (x == y) return x;
for(int i = 0; i < S; i++) {
if (up[x][i] != up[x][i]) {
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
long long d(int x, int y) {
return dist[x]+dist[y]-2*dist[lca(x,y)];
}
int find(int u, int p,int n) {
for(pair<int,int> i : adj[u]) {
if (i.first != p && !cen[i.first]) {
if (sz[i.first]*2 > n) return find(i.first,u,n);
}
}
return u;
}
void build(int u, int centr) {
dsz(u,centr);
int cent = find(u,centr,sz[u]);
cp[cent] = centr;
cen[cent] = true;
for(pair<int,int> i : adj[cent]) {
if (!cen[i.first]) build(i.first,cent);
}
}
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]});
mins[i] = -1;
}
mins[N-1] = -1;
n = N;
dep[0] = 0;
dist[0] = 0;
up[0][0] = 0;
dfsa(0,-1);
build(0,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vis;
for(int i = 0; i < S; i++) {
vis.push_back(X[i]);
mins[X[i]] = 0;
int curr = cp[X[i]];
while (curr != -1) {
vis.push_back(curr);
long long dis = d(X[i],curr);
if (mins[curr] == -1) mins[curr] = dis;
else mins[curr] = min(mins[curr],dis);
curr = cp[curr];
}
}
long long ret = 9223372036854775807;
for(int i = 0; i < T; i++) {
if (mins[Y[i]] != -1) ret = min(ret,mins[Y[i]]);
int curr = cp[Y[i]];
while(curr != -1) {
if (mins[curr] != -1) ret = min(ret,mins[curr] + d(Y[i],curr));
curr = cp[curr];
}
}
for(int i : vis) mins[i] = -1;
return ret;
}
Compilation message
factories.cpp: In function 'int lca(int, int)':
factories.cpp:50:22: warning: self-comparison always evaluates to false [-Wtautological-compare]
50 | if (up[x][i] != up[x][i]) {
| ~~~~~~~~ ^~ ~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
