#include "factories.h"
#include<bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
const int Max = 5e5 + 10;
const int LOG = 20;
const ll INF = 1e17 + 10;
int n;
vector<pair<int , int>> N[Max];
int sttime[Max] , edtime[Max] , ttime , par[Max][LOG] , h[Max];
ll dst[Max];
void DFS(int v , int p = 0)
{
sttime[v] = ++ttime;
for(int lg = 1 ; lg < LOG ; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1];
for(pair<int , int> u : N[v]) if(u.F != p) h[u.F] = h[v] + 1 , par[u.F][0] = v , dst[u.F] = dst[v] + u.S , DFS(u.F , v);
edtime[v] = ttime + 1;
}
int lca(int a , int b)
{
if(h[a] < h[b]) swap(a , b);
for(int lg = LOG ; lg-- ; ) if((h[a] - h[b]) & (1 << lg)) a = par[a][lg];
if(a == b) return a;
for(int lg = LOG ; lg-- ; ) if(par[a][lg] != par[b][lg]) a = par[a][lg] , b = par[b][lg];
return par[a][0];
}
void Init(int N , int A[] , int B[] , int D[])
{
n = N;
for(int i = 0 ; i < n - 1 ; i++) ::N[A[i]].pb(mp(B[i] , D[i])) , ::N[B[i]].pb(mp(A[i] , D[i]));
DFS(0);
}
ll DST[Max] , S[Max];
void dfs(vector<int> verts)
{
int R = 0; S[++R] = verts[0];
for(int i = 1 ; i < verts.size() ; i++)
{
while(sttime[S[R]] > sttime[verts[i]] || edtime[S[R]] <= sttime[verts[i]]) R--;
DST[S[R]] = min(DST[S[R]] , DST[verts[i]] + dst[verts[i]] - dst[S[R]]);
DST[verts[i]] = min(DST[verts[i]] , DST[S[R]] + dst[verts[i]] - dst[S[R]]);
S[++R] = verts[i];
}
}
long long Query(int S , int X[] , int T , int Y[])
{
vector<pair<int , int>> srt1 , srt2;
for(int i = 0 ; i < S ; i++) srt1.pb(mp(sttime[X[i]] , X[i])) , srt2.pb(mp(sttime[X[i]] , X[i]));
for(int i = 0 ; i < T ; i++) srt1.pb(mp(sttime[Y[i]] , Y[i])) , srt2.pb(mp(sttime[Y[i]] , Y[i]));
sort(srt1.begin() , srt1.end());
for(int i = 0 ; i < srt1.size() - 1 ; i++)
{
int l = lca(srt1[i].S , srt1[i + 1].S);
srt2.pb(mp(sttime[l] , l));
}
sort(srt2.begin() , srt2.end());
vector<int> verts;
for(pair<int , int> v : srt2) verts.pb(v.S) , DST[v.S] = INF;
verts.resize(unique(verts.begin() , verts.end()) - verts.begin());
for(int i = 0 ; i < S ; i++) DST[X[i]] = 0;
dfs(verts);
dfs(verts);
ll ans = INF;
for(int i = 0 ; i < T ; i++) ans = min(ans , DST[Y[i]]);
return ans;
}
Compilation message
factories.cpp: In function 'void dfs(std::vector<int>)':
factories.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 1 ; i < verts.size() ; i++)
| ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 0 ; i < srt1.size() - 1 ; i++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
12672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
12672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
