#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int up(int n, int k);
void DFS(int n);
void dijkstra(int n);
ll inf = LONG_LONG_MAX;
int n;
vector<vector<pair<int, ll>>> adj(500005);
vector<bool> vis(500005, 0);
vector<ll> dis(500005, inf), h(500005,0), parent(500005,0);
vector<pair<ll,ll>> outdeg(500005,{0,0});
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
vector<vector<int>> sparseT(500005, vector<int>(19));
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (int i = 0; i < N - 1; i++)
{
adj[A[i]].pb({B[i], D[i]});
adj[B[i]].pb({A[i], D[i]});
outdeg[A[i]].first++;
outdeg[A[i]].second = A[i];
outdeg[B[i]].first++;
outdeg[B[i]].second = B[i];
}
sort(outdeg.rbegin(),outdeg.rend());
//cout<<outdeg[0].second<<endl;
dijkstra(outdeg[0].second);
parent[outdeg[0].second] = outdeg[0].second;
DFS(outdeg[0].second);
for(int i=0; i < N; i++){
sparseT[i][0] = parent[i];
}
for(int j=1; j < 20; j++){
for(int i=0; i < N; i++){
sparseT[i][j] = parent[sparseT[i][j-1]];
}
}
}
long long Query(int S, int X[], int T, int Y[])
{
ll ans = inf;
for (int i = 0; i < S; i++){
for(int j = 0; j < T; j++){
for(int k = 1; k <= max(h[X[i]],h[Y[i]]); k++){
if(up(X[i],k) == up(Y[i],k)){
if(up[X[i],k] == outdeg[0].second){
ans = min(ans,dis[X[i]]+dis[Y[i]]);
}else{
ans = min(ans,(dis[X[i]]+dis[Y[i]])-dis[up(X[i],k)]);
}
}
}
}
}
return ans;
}
void up(int n, int k){
int act=n;
for(int p=0; p < 20; p++){
if(k & (1<<p)){
act = sparseT[act][p];
}
}
return act;
}
void DFS(int n){
vis[n] = 1;
for(auto [x,w]: adj[n]){
if(vis[x])continue;
h[x] = h[n]+1;
parent[x] = n;
DFS(x);
}
}
void dijkstra(int n)
{
dis[n] = 0;
pq.push({0,n});
while (!pq.empty())
{
int a = pq.top().second;
pq.pop();
if (vis[a])
continue;
vis[a] = 1;
for (auto [b, w] : adj[a])
{
if (dis[b] > dis[a] + w)
{
dis[b] = dis[a] + w;
pq.push({dis[b], b});
}
}
}
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:56:20: warning: value computed is not used [-Wunused-value]
56 | if(up[X[i],k] == outdeg[0].second){
| ~~~^
factories.cpp:56:20: warning: left operand of comma operator has no effect [-Wunused-value]
factories.cpp:56:23: warning: pointer to a function used in arithmetic [-Wpointer-arith]
56 | if(up[X[i],k] == outdeg[0].second){
| ^
factories.cpp:56:25: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
56 | if(up[X[i],k] == outdeg[0].second){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
factories.cpp: At global scope:
factories.cpp:69:6: error: ambiguating new declaration of 'void up(int, int)'
69 | void up(int n, int k){
| ^~
factories.cpp:8:5: note: old declaration 'int up(int, int)'
8 | int up(int n, int k);
| ^~
factories.cpp: In function 'void up(int, int)':
factories.cpp:77:10: error: return-statement with a value, in function returning 'void' [-fpermissive]
77 | return act;
| ^~~
