#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],distr[MAXN];
vector<int> dep;
int timer;
const ll INF = 1e18;
void dfs(int u, int p){
in[u] = ++timer;
par[u][0] = p;
for(auto edg : adj[u]){
if(edg.f != p){
distr[edg.f] = distr[u]+edg.s;
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]});
}
dfs(0,0);
for(int i = 1;i<=19;++i){
for(int j = 1;j<=N;++j){
par[j][i] = par[par[j][i-1]][i-1];
}
}
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>,vector<pair<ll,int>>,greater<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:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0;i<LS.size();++i){
| ~^~~~~~~~~~
factories.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0;i<LS.size();++i){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27484 KB |
Output is correct |
| 2 |
Correct |
1037 ms |
45752 KB |
Output is correct |
| 3 |
Correct |
921 ms |
45648 KB |
Output is correct |
| 4 |
Incorrect |
848 ms |
45884 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27228 KB |
Output is correct |
| 2 |
Correct |
1016 ms |
146880 KB |
Output is correct |
| 3 |
Incorrect |
1239 ms |
149840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
27484 KB |
Output is correct |
| 2 |
Correct |
1037 ms |
45752 KB |
Output is correct |
| 3 |
Correct |
921 ms |
45648 KB |
Output is correct |
| 4 |
Incorrect |
848 ms |
45884 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
