#include<bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
#define pii pair<ll,int>
#define _caminho second
#define _k first
#define INF 1e9
int t;
void find_sub( int v , int b1 , int b2 ,vector<int>& sub , vector<vector<int>>& A ) {
sub[v] = 1;
for( int viz : A[v] ) if( viz != b1 && viz != b2 )
{ find_sub( viz , v , b2 , sub , A ); sub[v] += sub[viz]; }
}
int find_centroid( int v, int b1, int b2 , int n , vector<int>& sub , vector<vector<int>>& A) {
for( int viz : A[v] ) if( viz != b1 && viz != b2 )
if( 2*sub[viz] > n ) return find_centroid( viz , v , b2 , n , sub , A );
return v;
}
void dfs( int v , int paiV , int b1 , int b2 , ll caminhoPai , int nDeAresta ,vector<pii>& kValidos ,vector<vector<ll>>& peso , vector<vector<int>>& A) {
//printf(" dfs %d , p%d , q%d , camp %lld , na%d \n" , v , b1 , b2 , caminhoPai , nDeAresta );
kValidos.push_back( make_pair( caminhoPai , nDeAresta) );
for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( viz != paiV && viz != b1 && viz != b2 )
dfs( viz , v , b1 , b2 , caminhoPai + peso[v][i] , nDeAresta+1 , kValidos , peso , A );
}
ll divide_and_conquer( int v , int b1 , int b2 , vector<int>& sub, vector<int>& minComK , vector<vector<ll>>& peso , vector<vector<int>>& A) {
++t;
int aux = v;
int k = minComK.size()-1;
find_sub( v , b1 , b2 , sub , A );
v = find_centroid( v , b1 , b2 , sub[v] , sub , A );
ll caminhoMin = INF;
// for( int i = 1 ; i < A.size() ; i++) {
// printf("%d :: " , i);
// for( int viz : A[i] ) printf(" %d" , viz );
// printf("\n");
// }
//printf(" divide and conquer : %d.start %d.centroid , [%d , %d]\n" ,aux , v , b1 , b2 );
//assert( t < 20 );
vector<int> kValidos;
for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( viz != b1 ) {
vector<pii> kValidosParaSub;
//printf(" vai por na dfs: %d , %d , %d %lld\n" , viz , v , b1 , peso[v][i]);
dfs( viz , v , b1 , b2 , peso[v][i] , 1 , kValidosParaSub , peso , A );
for( pii& e : kValidosParaSub ) if( e._k <= k ) caminhoMin = min( caminhoMin , e._caminho + ( long long ) minComK[ k - e._k ] );
for( pii& e : kValidosParaSub ) if( e._k <= k ) if(minComK[e._k] == INF ) {
kValidos.push_back(e._k);
minComK[e._k] = min( minComK[e._k] , e._caminho );
}
}
for( int e : kValidos ) minComK[e] = INF;
for( int viz : A[v] ) if( viz != b1 && viz != b2 )
caminhoMin = min( caminhoMin , divide_and_conquer( viz , v , b1 , sub , minComK , peso , A ) );
return caminhoMin;
}
int best_path(int N, int K, int H[][2], int L[]) {
vector<int> minComK( K+1 , INF );
vector<vector<int>> A(N+1);
vector<vector<ll>> peso(N+1);
for(int i = 0; i < N-1 ; i++ ) {
peso[++H[i][1]].push_back(L[i]);
peso[++H[i][0]].push_back(L[i]);
A[H[i][1]].push_back(H[i][0]);
A[H[i][0]].push_back(H[i][1]);
}
// for( int i = 1 ; i < A.size() ; i++) {
// printf("%d :: " , i);
// for( int viz : A[i] ) printf(" %d" , viz );
// printf("\n");
// }
vector<int> sub( N+1 , 0 );
int resp = ( int ) divide_and_conquer( 1 , 0 , 0 , sub , minComK , peso , A );
return ( resp == INF ) ? -1 : resp;
}
Compilation message
race.cpp: In function 'void dfs(int, int, int, int, ll, int, std::vector<std::pair<long long int, int> >&, std::vector<std::vector<long long int> >&, std::vector<std::vector<int> >&)':
race.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( viz != paiV && viz != b1 && viz != b2 )
| ~~^~~~~~~~~~~~~
race.cpp: In function 'll divide_and_conquer(int, int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<long long int> >&, std::vector<std::vector<int> >&)':
race.cpp:47:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( viz != b1 ) {
| ~~^~~~~~~~~~~~~
race.cpp:32:9: warning: unused variable 'aux' [-Wunused-variable]
32 | int aux = v;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1282 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1282 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1282 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1282 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
