#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int MAXN = 5e5+10;
vector<pair<int,ll>> adj[MAXN],newg[MAXN];
int par[MAXN][20],in[MAXN],out[MAXN];
ll dist[MAXN];
vector<int> dep;
vector<ll> distr;
int timer;
const ll INF = 1e18;
void dfs(int u, int p){
in[u] = ++timer;
for(auto edg : adj[u]){
if(edg.f != p){
dep[edg.f] = dep[u]+1;
distr[edg.f] = distr[u]+edg.s;
par[edg.f][0] = u;
dfs(edg.f,u);
}
}
out[u] = timer;
}
bool anc(int a, int b){
return in[a] <= in[b] && out[a] >= out[b];
}
bool cmp(int a, int b){
return in[a] < in[b];
}
void Init(int N, int A[], int B[], int D[]){
for(int i = 0;i<=N-2;++i){
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
dep = vector<int>(N+1,0); distr = vector<ll>(N+1,0); timer = 0;
dfs(0,0);
for(int i = 1;i<=19;++i){
for(int j = 1;j<=N;++j){
par[j][i] = par[j-1][par[j-1][i]];
}
}
for(int i = 0;i<=N;++i){
dist[i] = INF;
}
}
int lca(int a, int b){
if(anc(a,b)) return a;
if(anc(b,a)) return b;
for(int i = 19;i>=0;--i){
if(!anc(par[a][i],b)) a = par[a][i];
}
return par[a][0];
}
ll Query(int S, int X[], int T, int Y[]){
vector<int> LS;
for(int i = 0;i<S;++i){
LS.push_back(X[i]);
}
for(int i = 0;i<T;++i){
LS.push_back(Y[i]);
}
sort(LS.begin(),LS.end(),cmp); //sorted by DFS order
for(int i = 0;i<=S+T-2;++i){
LS.push_back(lca(LS[i],LS[i+1]));
}
LS.push_back(0);
sort(LS.begin(),LS.end(),cmp);
LS.resize(unique(LS.begin(),LS.end())-LS.begin());
vector<int> st;
for(int i = 0;i<LS.size();++i){
while(!st.empty() && !anc(st.back(),LS[i])) st.pop_back();
if(st.size()){
newg[st.back()].push_back({LS[i],distr[LS[i]]-distr[st.back()]});
newg[LS[i]].push_back({st.back(),distr[LS[i]]-distr[st.back()]});
}
st.push_back(LS[i]);
}
priority_queue<pair<ll,int>> pq;
for(int i = 0;i<S;++i){
pq.push({0ll,X[i]});
dist[X[i]] = 0ll;
}
while(!pq.empty()){
int u = pq.top().s, cd = pq.top().f; pq.pop();
if(cd != dist[u]) continue;
for(auto x : newg[u]){
if(cd+x.s < dist[x.f]){
dist[x.f] = cd+x.s;
pq.push({dist[x.f],x.f});
}
}
}
ll ret = INF;
for(int i = 0;i<T;++i){
ret = min(ret,dist[Y[i]]);
}
for(int i = 0;i<LS.size();++i){
dist[LS[i]] = INF;
newg[LS[i]].clear();
}
return ret;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int i = 0;i<LS.size();++i){
| ~^~~~~~~~~~
factories.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0;i<LS.size();++i){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
27224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
27480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
