#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int I = 5e5;
int N;
ll len[I], best[I];
int p[I], sz[I], in[I], vis[I], dep[I], par[I][19], st[2 * I][19];
vector<int> a;
vector<array<int, 2>> adj[I];
void dfs(int x, int p) {
in[x] = a.size();
a.push_back(x);
for (int i = 0; i < 18 && par[x][i] != -1; i++) {
par[x][i + 1] = par[par[x][i]][i];
}
for (auto [y, z] : adj[x]) {
if (y == p) continue;
par[y][0] = x;
dep[y] = dep[x] + 1;
len[y] = len[x] + z;
dfs(y, x);
a.push_back(x);
}
}
void init(int x, int p) {
sz[x] = 1;
for (auto [y, z] : adj[x]) {
if (vis[y] || y == p) continue;
init(y, x);
sz[x] += sz[y];
}
}
int find(int x, int p, int s) {
for (auto [y, z] : adj[x]) {
if (vis[y] || y == p) continue;
if (sz[y] * 2 > s) return find(y, x, s);
}
return x;
}
int cd(int x) {
init(x, -1);
x = find(x, -1, sz[x]);
vis[x] = 1;
for (auto [y, z] : adj[x]) {
if (!vis[y]) {
p[cd(y)] = x;
}
}
return x;
}
int f(int x, int y) {
return (x != -1 && (y == -1 || dep[x] < dep[y])) ? x : y;
}
void build() {
for (int i = 0; i < a.size(); i++) {
st[i][0] = a[i];
}
for (int j = 0; j < 18; j++) {
for (int i = 0; i + (2 << j) <= a.size(); i++) {
st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
}
}
}
int query(int l, int r) {
if (l == r) return -1;
int k = __lg(r - l);
return f(st[l][k], st[r - (1 << k)][k]);
}
int lca(int x, int y) {
int z = x;
for (int i = min(in[x], in[y]); i <= max(in[x], in[y]); i++) {
z = f(z, a[i]);
}
return z;
return query(min(in[x], in[y]), max(in[x], in[y]) + 1);
}
ll dis(int x, int y) {
return len[x] + len[y] - 2 * len[lca(x, y)];
}
void Init(int n, int A[], int B[], int D[]) {
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]});
}
for (int i = 0; i < N; i++) {
best[i] = 1e18;
for (int j = 0; j < 19; j++) {
par[i][j] = -1;
}
}
dfs(0, -1);
assert(a.size() == 2 * N - 1);
build();
p[cd(0)] = -1;
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
for (int j = X[i]; j != -1; j = p[j]) {
best[j] = min(best[j], dis(j, X[i]));
}
}
ll ans = 1e18;
for (int i = 0; i < T; i++) {
for (int j = Y[i]; j != -1; j = p[j]) {
ans = min(ans, best[j] + dis(j, Y[i]));
}
}
for (int i = 0; i < S; i++) {
for (int j = X[i]; j != -1; j = p[j]) {
best[j] = 1e18;
}
}
return ans;
}
Compilation message
factories.cpp: In function 'void build()':
factories.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
factories.cpp:60:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (int i = 0; i + (2 << j) <= a.size(); i++) {
| ~~~~~~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from factories.cpp:2:
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:94:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
94 | assert(a.size() == 2 * N - 1);
| ~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
41620 KB |
Output is correct |
| 2 |
Execution timed out |
8013 ms |
50052 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
41560 KB |
Output is correct |
| 2 |
Execution timed out |
8058 ms |
186392 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
41620 KB |
Output is correct |
| 2 |
Execution timed out |
8013 ms |
50052 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
