| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1117378 |
2024-11-23T13:16:59 Z |
batata1 |
Race (IOI11_race) |
C++17 |
|
1 ms |
504 KB |
#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;
vector<bool> previousCentroid;
void find_sub( int v , int paiV ,vector<int>& sub , vector<vector<int>>& A ) {
sub[v] = 1;
for( int viz : A[v] ) if( viz != paiV && !previousCentroid[viz] )
{ find_sub( viz , v , sub , A ); sub[v] += sub[viz]; }
}
int find_centroid( int v, int paiV , int n , vector<int>& sub , vector<vector<int>>& A) {
for( int viz : A[v] ) if( viz != paiV && !previousCentroid[viz] )
if( 2*sub[viz] > n ) return find_centroid( viz , v , n , sub , A );
return v;
}
void dfs( int v , int paiV , ll caminhoPai , int nDeAresta ,vector<pii>& kValidos ,vector<vector<ll>>& peso , vector<vector<int>>& A) {
//printf(" dfs %d , p%d , camp %lld , na%d \n" , v , paiV , 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 && !previousCentroid[viz] )
dfs( viz , v , caminhoPai + peso[v][i] , nDeAresta+1 , kValidos , peso , A );
}
ll divide_and_conquer( int v , 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 , v , sub , A );
v = find_centroid( v , v , 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\n" ,aux , v );
//assert( t < 30 );
vector<int> kValidos;
for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( !previousCentroid[viz] ) {
vector<pii> kValidosParaSub;
// printf(" vai por na dfs: %d , %d , %lld\n" , viz , v , peso[v][i]);
dfs( viz , v , 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;
previousCentroid[v] = true;
for( int viz : A[v] ) if(!previousCentroid[viz])
caminhoMin = min( caminhoMin , divide_and_conquer( viz , sub , minComK , peso , A ) );
return caminhoMin;
}
int best_path(int N, int K, int H[][2], int L[]) {
vector<int> minComK( K+1 , INF );
previousCentroid.resize(N+1 , false );
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 , sub , minComK , peso , A );
previousCentroid.clear();
return ( resp == INF ) ? -1 : resp;
}
Compilation message
race.cpp: In function 'void dfs(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:28:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( viz != paiV && !previousCentroid[viz] )
| ~~^~~~~~~~~~~~~
race.cpp: In function 'll divide_and_conquer(int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<long long int> >&, std::vector<std::vector<int> >&)':
race.cpp:49:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( !previousCentroid[viz] ) {
| ~~^~~~~~~~~~~~~
race.cpp:34:9: warning: unused variable 'aux' [-Wunused-variable]
34 | int aux = v;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
504 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
504 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
504 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
504 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
