#include "factories.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
const int MX = 5e5 + 7 ;
using namespace std ;
vector<pair<int,int> > adj[MX];
vector<int> adx[MX];
int st[MX], en[MX] , t ;
int up[MX][20] ;
int col[MX] ;
long long pref[MX] ;
void dfs(int x, int p ){
st[x] = ++ t ;
up[x][0] = p ;
for(int i = 1; i < 20 ; ++ i)
up[x][i] = up[ up[x][i-1]][i-1] ;
for(auto u : adj[x]){
if(u.first == p)continue ;
pref[u.first] = pref[x] + u.second ;
dfs(u.first , x) ;
}
en[x] = ++ t;
}
inline bool upper(int u , int v){return st[u] <= st[v] && en[v] <= en[u] ;}
inline bool cmp(int u ,int v){return st[u] < st[v] ;}
int lca(int u ,int v){
if(upper(u , v))return u ;
if(upper(v , u))return v ;
for(int i = 19 ; ~ i; -- i){
if(!upper(up[u][i] , v))
u = up[u][i] ;
}
return up[u][0] ;
}
void edge(int u , int v){
adx[u].push_back(v) ;
adx[v].push_back(u) ;
}
long long nrst[MX] ;
long long dfz(int x, int p){
long long ret = 1e18 ;
if(col[x]&2)ret = 0 ;
for(auto u : adx[x]){
if(u == p)continue ;
ret = min(ret , pref[u] - pref[x] + dfz(u , x)) ;
}
return nrst[x] = ret ;
}
long long answer = 0 ;
long long solve(int x, int p, long long ner = 1e18 ){
long long ret = (col[x]&1 == 1 ? nrst[x] : 1e18) ;
for(auto u : adx[x]){
if(u == p)continue;
long long add = 1e18 ;
for(auto j : adx[x]){
if(j == p || j == u)continue ;
add = min(add , nrst[j] + pref[j] - pref[x]) ;
}
ret = min(ret , solve(u , x, min(ner,add ) + pref[u] - pref[x] ) ) ;
}
if(col[x]&1){
answer = min(answer, min(ret , ner)) ;
}
return ret;
}
long long walk(int u, int v){
long long ret = 0 ;
while(u != v){
ret += pref[u] - pref[up[u][0]] ;
u = up[u][0] ;
}
return ret ;
}
long long build(vector<int> &vec){
answer = 1e18 ;
vec.push_back(0) ;
int sz = (int) vec.size() ;
sort(vec.begin() , vec.end() , cmp) ;
for(int i = 1; i < sz; ++ i){
vec.push_back(lca(vec[i-1] , vec[i])) ;
}
sort(vec.begin() , vec.end()) ;
vec.erase(unique(vec.begin() , vec.end()) , vec.end()) ;
vector<int> aux = {vec[0]} ;
for(int i = 1; i < (int) vec.size() ; ++ i){
int j = vec[i] ;
while(aux.size() > 1 && !upper(aux.back() ,j) ){
edge( aux[aux.size() - 2] , aux.back() ) ;
aux.pop_back() ;
}
aux.push_back(j) ;
}
while(aux.size() > 1){
edge(aux[aux.size() - 2] , aux.back()) ;
aux.pop_back() ;
}
for(int i = 0 ;i < (int) vec.size() ; ++ i){
for(int j = 0 ; j < (int) vec.size() ; ++ j){
if((col[vec[i]]&1) && (col[vec[j]]&2)){
int lc = lca(vec[i] , vec[j]) ;
answer = min(answer , pref[vec[i]] + pref[vec[j]] - 2ll * pref[lc] ) ;
}
}
}
// for(auto u : vec)cout<< u <<" " << col[u]<<".";cout<<"\n";
//dfz(0 , 0) ;
// long long ret = solve(aux[0] , aux[0]) ;
for(auto u : vec){
col[u] = 0 ;
adx[u].clear() ;
}
memset(nrst , 0 , sizeof nrst) ;
return answer ;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0 ;i < N - 1; ++ i){
int u = A[i] , v = B[i] , w = D[i] ;
adj[u].push_back({v , w}) ;
adj[v].push_back({u , w}) ;
}
dfs(0 , 0) ;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vec ;
for(int i = 0 ;i < S ; ++ i){
col[X[i]]|=1;
vec.push_back(X[i]) ;
}
for(int i = 0 ;i < T ; ++ i){
vec.push_back(Y[i]) ;
col[Y[i]]|=2;
}
build(vec) ;
long long ret = 1e18 ;
/*for(int i = 0 ; i < S ; ++ i){
for(int j = 0 ;j < T ; ++ j){
int lc = lca(X[i] , Y[j]) ;
ret = min(ret , pref[X[i]] + pref[Y[j]] - 2 * pref[lc]) ;
}
}
return ret ; */
return answer ;
}
Compilation message
factories.cpp: In function 'long long int solve(int, int, long long int)':
factories.cpp:63:35: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
63 | long long ret = (col[x]&1 == 1 ? nrst[x] : 1e18) ;
| ~~^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:154:19: warning: unused variable 'ret' [-Wunused-variable]
154 | long long ret = 1e18 ;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
299 ms |
28152 KB |
Output is correct |
2 |
Execution timed out |
8068 ms |
36928 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
27904 KB |
Output is correct |
2 |
Execution timed out |
8077 ms |
116796 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
299 ms |
28152 KB |
Output is correct |
2 |
Execution timed out |
8068 ms |
36928 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |