#include<bits/stdc++.h>
#include"factories.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 num , int A[] , int B[] , int D[])
{
n = num;
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];
}
}
ll 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());
//cout << "** ";
//for(auto v : srt1) cout << v.S << ' '; cout << '\n';
//cout << "*** ";
for(int i = 0 ; i < srt1.size() - 1 ; i++)
{
int l = lca(srt1[i].F , srt1[i + 1].F);
srt2.pb(mp(sttime[l] , l));
//cout << l << ' ';
}//cout << '\n';
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;
}
/*
int A[Max] , B[Max] , D[Max] , X[Max] , Y[Max];
int main()
{
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int n , q; cin >> n >> q;
for(int i = 0 ; i < n - 1 ; i++)
{
cin >> A[i] >> B[i] >> D[i];
}
Init(n , A , B , D);
for(int i = 0 ; i < q ; i++)
{
int s , t; cin >> s >> t;
for(int i = 0 ; i < s ; i++) cin >> X[i];
for(int i = 0 ; i < t ; i++) cin >> Y[i];
cout << Query(s , X , t , Y) << '\n';
}
}
*/
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 'll Query(int, int*, int, int*)':
factories.cpp:62: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]
62 | for(int i = 0 ; i < srt1.size() - 1 ; i++)
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
12800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
12268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
12800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
