#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ld long double
#define cd complex<ld>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pld pair<ld,ld>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std ;
ll n ;
ll num = 700 ;
vector<pll> T[500005] ;
ll depth[500005] ;
ll dis[500005] ;
ll lg2[1000005] ;
ll Left[500005] ;
vector<ll> euler ;
vector<pll> sparse[20] ;
void build()
{
for(int i = 0 ; i< 20 ; i++)
{
if((1<<i)>euler.size()) break ;
if(i==0)
{
sparse[0].assign(euler.size() , {0 , 0}) ;
for(int j = 0 ; j< euler.size() ; j++)
{
sparse[0][j] = {depth[euler[j]], euler[j]} ;
}
}
else
{
sparse[i].assign(euler.size()+1-(1<<i) , {0 , 0}) ;
for(int j = 0 ; j< euler.size()-(1<<i)+1 ; j++)
{
sparse[i][j] = min(sparse[i-1][j] , sparse[i-1][j+(1<<(i-1))]) ;
}
}
}
}
ll LCA(ll u , ll v)
{
u = Left[u] , v = Left[v] ;
if(u>v) swap(u , v) ;
ll k = lg2[v-u+1] ;
pll x = min(sparse[k][u] , sparse[k][v-(1<<k)+1]) ;
return x.se ;
}
void dfs(ll v , ll par)
{
Left[v] = euler.size() ;
euler.push_back(v) ;
for(int i = 0 ; i< T[v].size() ; i++)
{
if(T[v][i].fi==par) continue ;
dis[T[v][i].fi] = T[v][i].se+dis[v] ;
depth[T[v][i].fi] = depth[v]+1 ;
dfs(T[v][i].fi , v) ;
euler.push_back(v) ;
}
}
void Init(int N, int A[], int B[], int D[])
{
num = n ;
n = N ;
for(int i = 0 ; i< n-1 ; i++)
{
T[A[i]].push_back(mp(B[i] , D[i])) ;
T[B[i]].push_back(mp(A[i] , D[i])) ;
}
for(int i = 2 ; i<= 1000000 ; i++) lg2[i] = lg2[i/2]+1 ;
dfs(0 , -1);
build() ;
}
ll distance(ll u , ll v)
{
ll k = LCA(u , v) ;
//cout << u << " " << v << " " << k << "\n" ;
//cout << dis[u]+dis[v]-2*dis[k] << "\n" ;
return dis[u]+dis[v]-2*dis[k] ;
}
ll dist[500005] = {} ;
bool check[500005] = {} ;
ll Query(int N, int X[], int M, int Y[])
{
//cout<< N << " " << M << "\n" ;
if(N*M>num)
{
for(int i = 0 ; i<= n ; i++)
{
dist[i] = LLONG_MAX ;
check[i] = 0 ;
}
priority_queue<pll , vector<pll> , greater<pll>> q ;
for(int i = 0 ; i< N ;i++)
{
dist[X[i]] = 0 ;
q.push(mp(0 , X[i])) ;
}
while(!q.empty())
{
ll le = q.top().fi , x = q.top().se;
q.pop() ;
//cout << le << " " << x << "\n" ;
if(le!=dist[x]||check[x]) continue ;
check[x] = 1 ;
//cout << T[x][0].fi << "\n" ;
for(int i = 0 ; i< T[x].size() ; i++)
{
if(dist[T[x][i].fi]>T[x][i].se+le)
{
dist[T[x][i].fi] = T[x][i].se+le ;
q.push(mp(dist[T[x][i].fi] , T[x][i].fi)) ;
}
}
}
ll ans = LLONG_MAX ;
for(int i = 0 ; i< M ; i++)
{
ans = min(ans , dist[Y[i]]) ;
}
return ans ;
}
else
{
ll ans = LLONG_MAX ;
for(int i = 0 ; i< N ; i++)
{
for(int j = 0 ; j< M ; j++)
{
ans = min(ans , distance(X[i] , Y[j])) ;
}
}
return ans ;
}
return 0;
}
Compilation message
factories.cpp: In function 'void build()':
factories.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | if((1<<i)>euler.size()) break ;
| ~~~~~~^~~~~~~~~~~~~
factories.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int j = 0 ; j< euler.size() ; j++)
| ~^~~~~~~~~~~~~~
factories.cpp:39:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int j = 0 ; j< euler.size()-(1<<i)+1 ; j++)
| ~^~~~~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs(long long int, long long int)':
factories.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 0 ; i< T[v].size() ; i++)
| ~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:113:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int i = 0 ; i< T[x].size() ; i++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
20308 KB |
Output is correct |
| 2 |
Correct |
2704 ms |
31588 KB |
Output is correct |
| 3 |
Correct |
2763 ms |
31580 KB |
Output is correct |
| 4 |
Correct |
2174 ms |
31568 KB |
Output is correct |
| 5 |
Correct |
1721 ms |
31828 KB |
Output is correct |
| 6 |
Correct |
2988 ms |
31908 KB |
Output is correct |
| 7 |
Correct |
2646 ms |
31548 KB |
Output is correct |
| 8 |
Correct |
2500 ms |
31544 KB |
Output is correct |
| 9 |
Correct |
1580 ms |
31996 KB |
Output is correct |
| 10 |
Correct |
2991 ms |
31552 KB |
Output is correct |
| 11 |
Correct |
2655 ms |
31412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
20128 KB |
Output is correct |
| 2 |
Execution timed out |
8051 ms |
379288 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
20308 KB |
Output is correct |
| 2 |
Correct |
2704 ms |
31588 KB |
Output is correct |
| 3 |
Correct |
2763 ms |
31580 KB |
Output is correct |
| 4 |
Correct |
2174 ms |
31568 KB |
Output is correct |
| 5 |
Correct |
1721 ms |
31828 KB |
Output is correct |
| 6 |
Correct |
2988 ms |
31908 KB |
Output is correct |
| 7 |
Correct |
2646 ms |
31548 KB |
Output is correct |
| 8 |
Correct |
2500 ms |
31544 KB |
Output is correct |
| 9 |
Correct |
1580 ms |
31996 KB |
Output is correct |
| 10 |
Correct |
2991 ms |
31552 KB |
Output is correct |
| 11 |
Correct |
2655 ms |
31412 KB |
Output is correct |
| 12 |
Correct |
32 ms |
20128 KB |
Output is correct |
| 13 |
Execution timed out |
8051 ms |
379288 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
