#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int lg2(unsigned long long i) { return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1; }
const int NM = 1e6+6;
vector<pair<int, long long>> g[NM];
vector<pair<int, long long>> g_aux[NM];
int t_in[NM];
int t_out[NM];
pair<int, int> sp[21][NM];
int up[21][NM];
long long up_dist[21][NM];
const long long INF = 1e18+5;
int n;
vector<pair<int, int>> euler_tour;
int mark[NM];
long long res_query = INF;
long long dp1[NM], dp2[NM];
void dfs(int u, int p, int d){
t_in[u] = euler_tour.size();
up[0][u] = p;
for (int i = 1; i <= 20; i++){
up[i][u] = up[i - 1][up[i - 1][u]];
up_dist[i][u] = up_dist[i - 1][u] + up_dist[i - 1][up[i - 1][u]];
}
euler_tour.push_back({d, u});
for (auto& e : g[u]){
int &v = e.first;
long long &w = e.second;
if (v == p) continue;
up_dist[0][v] = w;
dfs(v, u, d + 1);
euler_tour.push_back({d, u});
}
t_out[u] = euler_tour.size() - 1;
}
void build_sparse_table(){
for (int i = 0; i < (int)euler_tour.size(); i++){
sp[0][i] = euler_tour[i];
}
for (int i = 1; i <= 20; i++){
for (int j = 0; j < (int)euler_tour.size() - (1 << (i - 1)); j++){
sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
}
inline pair<int, int> LCA(int u, int v){
int l = t_in[u];
int r = t_in[v];
if (l > r) swap(l, r);
int lvl = lg2(r - l + 1);
return min(sp[lvl][l], sp[lvl][r - (1 << lvl) + 1]);
}
inline long long dist_to_ancestor(int u, int v){
int dept = euler_tour[t_in[u]].first - euler_tour[t_in[v]].first;
long long res = 0;
for (int i = 20; i >= 0; i--){
if ((dept >> i) & 1){
res += up_dist[i][u];
u = up[i][u];
}
}
return res;
}
void dfs2(int u, int p){
if (mark[u] == 2){
dp2[u] = 0;
}else if (mark[u] == 1){
dp1[u] = 0;
}
for (auto v : g_aux[u]){
if (v.first == p) continue;
dfs2(v.first, u);
res_query = min(res_query, min(dp1[u] + dp2[v.first] + v.second, dp2[u] + dp1[v.first]+ v.second));
dp1[u] = min(dp1[u], dp1[v.first] + v.second);
dp2[u] = min(dp2[u], dp2[v.first] + v.second);
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < N; i++){
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0, 0);
build_sparse_table();
}
long long Query(int S, int X[], int T, int Y[]) {
res_query = INF;
vector<int> a;
memset(mark, 0, sizeof mark);
fill(begin(dp1), end(dp1), INF);
fill(begin(dp2), end(dp2), INF);
for (int i = 0; i < S; i++){
a.push_back(X[i]);
mark[X[i]] = 1;
}
for (int i = 0; i < T; i++){
a.push_back(Y[i]);
mark[Y[i]] = 2;
}
for (int i = 0; i < n; i++){
g_aux[i].clear();
}
sort(a.begin(), a.end(), [&](const int &x, const int &y){
return t_in[x] < t_in[y];
});
for (int i = 0; i < S + T - 1; i ++){
int lca = LCA(a[i], a[i + 1]).second;
if (!mark[lca]){
a.push_back(lca);
mark[lca] = 3;
}
}
sort(a.begin(), a.end(), [&](const int &x, const int &y){
return t_in[x] < t_in[y];
});
stack<int> st;
for (int i = 0; i < int(a.size()); i++){
while(!st.empty() && euler_tour[t_in[st.top()]].first >= euler_tour[t_in[a[i]]].first){
st.pop();
}
if (st.empty()){
st.push(a[i]);
continue;
}
int u = st.top();
if (u != a[i]){
long long w = dist_to_ancestor(a[i], u);
g_aux[u].push_back({a[i], w});
g_aux[a[i]].push_back({u, w});
}
st.push(a[i]);
}
dfs2(a[0], -1);
return res_query;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
755 ms |
67804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
777 ms |
67612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
755 ms |
67804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
