Submission #1117398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117398		batata1	Race (IOI11_race)	C++17	0 / 100	1 ms	336 KiB

race

#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) );
    if( !A[v].empty() ) 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;
    if( !A[v].empty() ) for( int i = 0 , viz = A[v][0] ; i < A[v].size() ; viz = A[v][++i] ) if( !previousCentroid[viz] ) {
        vector<pii> kValidosParaSub;
        if( peso[v][i] == k ) caminhoMin = 1;
        //printf("   validos para sub :%d\n" , viz);
        //for( pii e : kValidosParaSub ) printf("%lld %d\n" , e._k , e._caminho);
         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 (stderr)

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:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if( !A[v].empty() ) 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:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     if( !A[v].empty() ) 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;
      |         ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57