#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
ll oo=1e18;
vector<pair<int,ll>> graph[500003];
ll iter=0;
ll pre[500003];
ll post[500003];
ll dep[500003];
ll real_dep[500003];
ll jmp[500003][20];
int lca(int a, int b){
if (dep[a]<dep[b])swap(a,b);
for (int i = 19; i>=0; i--){
if (dep[jmp[a][i]]>=dep[b])a=jmp[a][i];
}
if (a==b)return a;
for (int i = 19; i>=0; i--){
if (jmp[a][i]!=jmp[b][i]){
a=jmp[a][i];
b=jmp[b][i];
}
}
return jmp[a][0];
}
ll dist(int a, int b){
if (pre[a]<=pre[b] && post[a]>=post[b])return real_dep[b]-real_dep[a];
if (pre[a]>=pre[b] && post[a]<=post[b])return real_dep[a]-real_dep[b];
return real_dep[a]+real_dep[b]-2*real_dep[lca(a,b)];
}
void prep(int v, int p){
pre[v]=iter++;
jmp[v][0]=p;
for (int i = 1; i<20; i++)jmp[v][i]=jmp[jmp[v][i-1]][i-1];
for (auto [u,d] : graph[v]){
if (u==p)continue;
dep[u]=dep[v]+1;
real_dep[u]=real_dep[v]+d;
prep(u,v);
}
post[v]=iter++;
}
int n;
void Init(int N, int A[], int B[], int D[]){
n=N;
for (int i = 0; i<N-1; i++){
graph[A[i]].push_back({B[i],D[i]});
graph[B[i]].push_back({A[i],D[i]});
}
prep(0,0);
}
ll odl[500003];
ll fin[500003];
ll dp[500003][2];
map<int,vector<int>> mp;
ll dfs(int v){
if (fin[v])dp[v][fin[v]-1]=0;
ll odp=oo;
for (auto u : mp[v]){
odp=min(odp,dfs(u));
dp[v][0]=min(dp[v][0],dp[u][0]+real_dep[u]-real_dep[v]);
dp[v][1]=min(dp[v][1],dp[u][1]+real_dep[u]-real_dep[v]);
}
return min(odp,dp[v][0]+dp[v][1]);
}
ll Query(int S, int X[], int T, int Y[]){
vector<int> tab;
for (int i = 0; i<S; i++)tab.push_back(X[i]);
for (int i = 0; i<T; i++)tab.push_back(Y[i]);
for (int i = 0; i<S; i++)fin[X[i]]=1;
for (int i = 0; i<T; i++)fin[Y[i]]=2;
sort(tab.begin(),tab.end(), [](int a, int b){return pre[a]<pre[b];});
int powt=tab.size();
for (int i = 0; i<powt-1; i++){
if ((pre[tab[i+1]]-pre[tab[i]])*(post[tab[i+1]]-post[tab[i]])>=0){
int dod=lca(tab[i],tab[i+1]);
if (!fin[dod])tab.push_back(dod);
}
}
sort(tab.begin(),tab.end(), [](int a, int b){return pre[a]<pre[b];});
for (auto u : tab)dp[u][0]=dp[u][1]=oo;
ll ans=oo;
stack<int> st;
st.push(tab[0]);
for (int i = 1; i<tab.size(); i++){
while(st.size() && post[st.top()]<post[tab[i]]){
st.pop();
}
if (st.size())mp[st.top()].push_back(tab[i]);
st.push(tab[i]);
}
ans=dfs(tab[0]);
mp.clear();
for (auto u : tab)dp[u][0]=dp[u][1]=0;
for (int i = 0; i<T; i++)fin[Y[i]]=0;
return ans;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:94:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i = 1; i<tab.size(); i++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
296 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
