#include "factories.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
set<pair<int, ll>> graph[500000];
int tin[500000], tout[500000], timer = 0, anc[500000][19];
ll to_anc[500000][19];
int subtree[500000], c_par[500000];
ll c_dist[500000];
void dfs(int node = 0, int parent = -1) {
tin[node] = timer++;
for (int i = 1; i < 20; i++) {
anc[node][i] = anc[anc[node][i - 1]][i - 1];
to_anc[node][i] = to_anc[node][i - 1] + to_anc[anc[node][i - 1]][i - 1];
}
for (pair<int, ll> i : graph[node]) if (i.first != parent) {
anc[i.first][0] = node;
to_anc[i.first][0] = i.second;
dfs(i.first, node);
}
tout[node] = timer++;
}
inline bool is_ancestor(int u, int v) { return (tin[u] <= tin[v] && tout[u] >= tout[v]); }
ll dist(int u, int v) {
ll ans = 0;
for (int i = 18; ~i; i--) if (!is_ancestor(anc[u][i], v)) {
ans += to_anc[u][i];
u = anc[u][i];
}
if (!is_ancestor(u, v)) ans += to_anc[u][0];
for (int i = 18; ~i; i--) if (!is_ancestor(anc[v][i], u)) {
ans += to_anc[v][i];
v = anc[v][i];
}
if (!is_ancestor(v, u)) ans += to_anc[v][0];
return ans;
}
void get_subtree_sizes(int node, int parent = -1) {
subtree[node] = 1;
for (pair<int, ll> i : graph[node]) if (i.first != parent) {
get_subtree_sizes(i.first, node);
subtree[node] += subtree[i.first];
}
}
int get_centroid(int node, int parent, int tree_size) {
for (pair<int, ll> i : graph[node])
if (i.first != parent && subtree[i.first] > tree_size)
return get_centroid(i.first, node, tree_size);
return node;
}
void centroid_decomp(int node = 0, int prv_centroid = -1) {
get_subtree_sizes(node);
int centroid = get_centroid(node, -1, subtree[node] / 2);
c_par[centroid] = prv_centroid;
for (pair<int, ll> i : graph[centroid]) {
graph[i.first].erase({centroid, i.second});
centroid_decomp(i.first, centroid);
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
graph[A[i]].insert({B[i], D[i]});
graph[B[i]].insert({A[i], D[i]});
}
dfs();
centroid_decomp();
memset(c_dist, 0x3f, sizeof c_dist);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
int curr = X[i];
while (curr != -1) {
c_dist[curr] = min(c_dist[curr], dist(X[i], curr));
curr = c_par[curr];
}
}
ll ans = 0x3f3f3f3f3f3f3f3f;
for (int i = 0; i < T; i++) {
int curr = Y[i];
while (curr != -1) {
ans = min(ans, c_dist[curr] + dist(Y[i], curr));
curr = c_par[curr];
}
}
for (int i = 0; i < S; i++) {
int curr = X[i];
while (curr != -1) {
c_dist[curr] = 0x3f3f3f3f3f3f3f3f;
curr = c_par[curr];
}
}
return ans;
}
Compilation message
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:16:22: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
16 | anc[node][i] = anc[anc[node][i - 1]][i - 1];
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:15:23: note: within this loop
15 | for (int i = 1; i < 20; i++) {
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
28268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
28012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
28268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
