#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct lca{
static const int LG = 24;
vector<int> tin, tout;
vector<pair<ll, int>> sp[LG];
void start(int n){
tin.resize(n), tout.resize(n);
sp[0].reserve(n*2);
}
void build(){
for (int i=1; i<LG; i++){
sp[i].resize(sp[0].size());
for (int j=0; j + (1 << (i-1)) < sp[0].size(); j++){
sp[i][j] = min(sp[i-1][j], sp[i-1][j + (1 << (i-1))]);
}
}
}
int query(int a, int b){
a = tin[a], b = tin[b];
if (a > b) swap(a, b);
int lg = 31 - __builtin_clz(b - a + 1);
return min(sp[lg][a], sp[lg][b - (1<<lg) + 1]).second;
}
bool is_par(int p, int v){
return tin[p] <= tin[v] && tout[v] <= tout[p];
}
void sort_set(vector<int> &s){
sort(s.begin(), s.end(), [&](int a, int b){return tin[a] < tin[b];});
s.resize(unique(s.begin(), s.end()) - s.begin());
}
ll get_depth(int v){
return sp[0][tin[v]].first;
}
} lca;
int n;
vector<vector<pair<int, int>>> g;
void dfs(int v, int p, ll d){
lca.sp[0].emplace_back(d, v);
lca.tin[v] = lca.sp[0].size()-1;
for (pair<int, int> e: g[v]){
if (e.first == p) continue;
dfs(e.first, v, d + e.second);
lca.sp[0].emplace_back(d, v);
}
lca.tout[v] = lca.sp[0].size()-1;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
g.resize(n);
for (int i=0; i<n-1; i++){
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
lca.start(n);
dfs(0, -1, 0);
lca.build();
}
ll solve(vector<int> &x, vector<int> &y){
sort(x.begin(), x.end()); sort(y.begin(), y.end());
vector<int> s = x; s.insert(s.end(), y.begin(), y.end());
lca.sort_set(s);
for (int i=s.size()-1; i; i--) s.push_back(lca.query(s[i], s[i-1]));
lca.sort_set(s);
vector<int> p(s.size());
p[0] = -1;
vector<int> st = {0};
for (int i=1; i<s.size(); i++){
while (!lca.is_par(s[st.back()], s[i])) st.pop_back();
p[i] = st.back();
st.push_back(i);
}
vector<ll> min1(s.size(), 1e18), min2(s.size(), 1e18);
for (int i=0; i<s.size(); i++){
bool xs = binary_search(x.begin(), x.end(), s[i]);
if (xs) min1[i] = 0;
bool ys = binary_search(y.begin(), y.end(), s[i]);
if (ys) min2[i] = 0;
}
for (int i=s.size()-1; i; i--){
ll dist = lca.get_depth(s[i]) - lca.get_depth(s[p[i]]);
min1[p[i]] = min(min1[p[i]], min1[i] + dist);
min2[p[i]] = min(min2[p[i]], min2[i] + dist);
}
ll result = LLONG_MAX;
for (int i=0; i<s.size(); i++){
result = min(result, min1[i] + min2[i]);
}
return result;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> x(S), y(T);
copy(X, X+S, x.begin()), copy(Y, Y+S, y.begin());
return solve(x, y);
}
Compilation message
factories.cpp: In member function 'void lca::build()':
factories.cpp:17:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int j=0; j + (1 << (i-1)) < sp[0].size(); j++){
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
factories.cpp: In function 'll solve(std::vector<int>&, std::vector<int>&)':
factories.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int i=1; i<s.size(); i++){
| ~^~~~~~~~~
factories.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i=0; i<s.size(); i++){
| ~^~~~~~~~~
factories.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i=0; i<s.size(); i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1748 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
1748 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
