oj.uz

답안 #1117387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117387 2024-11-23T13:28:30 Z batata1 경주 (Race) (IOI11_race) C++17
0 / 100
 1 ms 508 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) );
    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;
    //    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: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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 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 504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 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 504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 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 504 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 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 504 KB Output isn't correct
9 Halted 0 ms 0 KB -