#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 ;
bool vis[MX];
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) == 1){
answer = min(answer, min(ret , ner)) ;
}
return ret;
}
long long build(vector<int> &vec){
answer = 1e18 ;
for(int i = 0 ;i < MX ; ++ i)nrst[i] = 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) ;
memset(vis , 0 , sizeof vis) ;
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 ;
return answer ;
}
Compilation message
factories.cpp: In function 'long long int build(std::vector<int>&)':
factories.cpp:120:19: warning: unused variable 'ret' [-Wunused-variable]
120 | long long ret = solve(aux[0] , aux[0]) ;
| ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:149:19: warning: unused variable 'ret' [-Wunused-variable]
149 | long long ret = 1e18 ;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
269 ms |
28544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
249 ms |
28468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
269 ms |
28544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
