#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int,int>>> g;
int n;
const int nmax = 500005,LOG = 21;
int sz[nmax],is_centroid[nmax],depth[nmax],cp[nmax],mput2[2 * nmax];
ll sol[nmax];
int in_reset[nmax];
long long rdis[nmax];
const ll inf = (1LL << 60);
void get_size(int node, int parent) {
sz[node] = 1;
for (auto k : g[node]) {
if (k.first == parent || is_centroid[k.first]) {
continue;
}
get_size(k.first, node);
sz[node] += sz[k.first];
}
}
int get_centroid(int node, int parent, int nr_nodes) {
int half = nr_nodes / 2;
for (auto k : g[node]) {
if (k.first == parent || is_centroid[k.first]) {
continue;
}
if (sz[k.first] > half) {
return get_centroid(k.first, node, nr_nodes);
}
}
return node;
}
void build_centroid(int node, int centroid_parent) {
get_size(node, 0);
int centroid = get_centroid(node,0, sz[node]);
cp[centroid] = centroid_parent;
is_centroid[centroid] = 1;
for (auto k : g[centroid]) {
if (is_centroid[k.first] == 0) {
build_centroid(k.first , centroid);
}
}
}
vector<int> euler;
int tin[nmax],tout[nmax],cnt = 0;
void get_depth(int node, int parent) {
for (auto k : g[node]) {
if (k.first == parent) {
continue;
}
depth[k.first] = depth[node] + 1;
rdis[k.first] = rdis[node] + k.second;
get_depth(k.first, node);
}
}
void get_euler(int node, int parent) {
tin[node] = ++cnt;
euler.push_back(node);
for (auto k : g[node]) {
if (k.first == parent) {
continue;
}
get_euler(k.first , node);
}
tout[node] = ++cnt;
euler.push_back(depth[node]);
}
struct Wow {
int node;
bool operator < (const Wow &other) const {
return depth[node] < depth[other.node];
}
};
Wow rmq[LOG][nmax];
void build_rmq() {
for (int i = 1; i < euler.size(); i++) {
rmq[0][i].node = euler[i];
}
mput2[1] = 0;
for (int i = 2; i <= 2 * n; i++) {
mput2[i] = mput2[i / 2] + 1;
}
for (int lvl = 1; lvl < LOG; lvl++) {
for (int i = 1; i < (int)euler.size() - (1 << lvl) + 1; i++) {
rmq[lvl][i] = min(rmq[lvl-1][i] , rmq[lvl - 1][i + (1 << (lvl-1))]);
}
}
}
int query_rmq(int l, int r) {
if (l > r) {
swap(l,r);
}
int put = mput2[r - l + 1];
return min(rmq[put][l], rmq[put][r - (1 << put) + 1]).node;
}
int get_lca(int u, int v) {
return query_rmq(tin[u],tin[v]);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
g.resize(n + 1);
for (int i = 1; i < n; i++) {
A[i - 1]++;
B[i - 1]++;
g[A[i - 1]].push_back({B[i - 1] , D[i - 1]});
g[B[i - 1]].push_back({A[i - 1], D[i - 1]});
}
for (int i = 1; i <= n; i++) {
sol[i] = inf;
}
get_depth(1,0);
euler.push_back(-1);
get_euler(1, 0);
build_rmq();
build_centroid(1, 0);
return;
}
ll get_dis(int u, int v) {
int lca = get_lca(u,v);
return rdis[u] + rdis[v] - 2 * rdis[lca];
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S;i++) {
X[i]++;
}
for (int i = 0; i < T;i++){
Y[i]++;
}
queue<int> reset_nodes;
for (int i = 1; i <= S; i++) {
for (int node = X[i - 1]; node != 0; node = cp[node]) {
sol[node] = min(sol[node] , get_dis(node, X[i - 1]));
if (!in_reset[node]) {
in_reset[node] = 1;
reset_nodes.push(node);
}
}
}
ll res = inf;
for (int i = 1; i <= T; i++) {
for (int node = Y[i - 1]; node != 0; node = cp[node]) {
res = min(res, sol[node] + get_dis(node, Y[i - 1]));
}
}
while(!reset_nodes.empty()) {
in_reset[reset_nodes.front()] = 0;
sol[reset_nodes.front()] = inf;
reset_nodes.pop();
}
return res;
}
Compilation message
factories.cpp: In function 'void build_rmq()':
factories.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 1; i < euler.size(); i++) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
