#include<bits/stdc++.h>
#include "factories.h"
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define f first
#define s second
#define pii pair<int,ll>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const int LIM=5e5;
const ll INF=1e18;
const string name="template";
int n,m;
vector<pii> adj[LIM+5],adj_vt[LIM+5];
int time_dfs=0;
pii euler_tour[2*LIM+5],sparse_table[20][2*LIM+5];
int tin[LIM+5],tout[LIM+5],h[LIM+5];
ll dist_X[LIM+5],dist_Y[LIM+5],dist[LIM+5];
vector<int> List;
int color[LIM+5];
vector<int> st;
void dfs(int u,int parent,int depth){
h[u] = depth;
tin[u] = time_dfs;
euler_tour[time_dfs++] = {depth,u};
for(auto v:adj[u]){
if(v.f==parent) continue;
dfs(v.f,u,depth + 1);
euler_tour[time_dfs++] = {depth,u};
dist[v.f] = dist[u] + v.s;
}
tout[u] = time_dfs;
}
int lca(int u,int v){
if(tin[u]>tin[v]){
swap(u,v);
}
int bt = 31 - __builtin_clz(tin[v]-tin[u]+1);
pii mn = min(sparse_table[bt][tin[u]],sparse_table[bt][tin[v] - (1<<bt) + 1]);
return mn.s;
}
ll Dist(int u,int v){
int LCA = lca(u,v);
return dist[u] + dist[v]- 2*dist[LCA];
}
bool cmp(int a,int b){
return tin[a]<tin[b];
}
bool isSubtree(int u,int v)
{
return tin[u]<=tin[v] && tin[v]<=tout[u];
}
void dfs_to_find_sol(int u,int parent){
for(auto v:adj_vt[u]){
if(v.f==parent) continue;
dfs_to_find_sol(v.f,u);
dist_X[u] = min(dist_X[u],dist_X[v.f] + v.s);
dist_Y[u] = min(dist_Y[u],dist_Y[v.f] + v.s);
}
}
void Init(int N, int A[], int B[], int D[]){
n=N;
for(int i=0;i<n-1;++i){
A[i]++;
B[i]++;
}
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=1;i<=n;++i){
dist_X[i]=INF;
dist_Y[i]=INF;
color[i] = -1;
}
dfs(1,0,0);
for(int i=0;i<time_dfs;++i){
sparse_table[0][i] = euler_tour[i];
}
for(int i=1;i<20;++i){
for(int j=0;j+(1<<i)-1<time_dfs;++j){
sparse_table[i][j] = min(sparse_table[i-1][j],sparse_table[i-1][j + (1<<(i-1))]);
}
}
}
long long Query(int S, int X[], int T, int Y[]){
for(auto x:List){
color[x] = -1;
adj_vt[x].clear();
dist_X[x]=dist_Y[x]=INF;
}
List.clear();
st.clear();
for(int i=0;i<S;++i){
List.push_back(++X[i]);
color[X[i]] = 0;
dist_X[X[i]]=0;
dist_Y[X[i]]=INF;
}
for(int i=0;i<T;++i){
List.push_back(++Y[i]);
if(color[Y[i]]==0){
return 0;
}
color[Y[i]]=1;
dist_X[Y[i]]=INF;
dist_Y[Y[i]]=0;
}
sort(List.begin(),List.end(),cmp);
for(int i=1;i<S+T;++i){
int LCA = lca(List[i-1],List[i]);
if(color[LCA]==-1){
dist_X[LCA] = dist_Y[LCA] = INF;
}
List.push_back(LCA);
}
int root;
sort(List.begin(),List.end(),cmp);
List.erase(unique(List.begin(),List.end()),List.end());
for(int i=0;i<List.size();++i){
int u = List[i];
while(st.size()>=2 && !isSubtree(st.back(),u)){
int x = st[st.size()-2];
int y= st.back();
ll w=Dist(x,y);
adj_vt[x].push_back({y,w});
adj_vt[y].push_back({x,w});
root=x;
st.pop_back();
}
st.push_back(u);
}
while(st.size()>=2){
int x = st[st.size()-2];
int y= st.back();
ll w=Dist(x,y);
adj_vt[x].push_back({y,w});
adj_vt[y].push_back({x,w});
root=x;
st.pop_back();
}
dfs_to_find_sol(root,0);
ll ans=INF;
for(auto x:List){
ans = min(ans,dist_X[x] + dist_Y[x]);
}
return ans;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:141:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int i=0;i<List.size();++i){
| ~^~~~~~~~~~~~
factories.cpp:163:17: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
163 | dfs_to_find_sol(root,0);
| ~~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
24444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
24148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
24444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
