Submission #552266

#	Time	Username	Problem	Language	Result	Execution time	Memory
552266		QuantumK9	Crocodile's Underground City (IOI11_crocodile)	C++17	46 / 100	3 ms	852 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;

vector< vector< pair<int,int> > > connect;
vector<bool> explored, isEnd;

int delve( int i ){

  explored[i] = true;

  if( isEnd[i] ){ return 0; }

  vector<int> poss;

  for( int j = 0; j < connect[i].size(); j++ ){
    if ( !explored[ connect[i][j].first ] ){
      int val = delve( connect[i][j].first );
      if ( val != -1 ){
        poss.pb( val + connect[i][j].second );
      }
    }
  }

  sort( poss.begin(), poss.end() );

  if ( poss.size() < 2 ){ return -1; }
  else{ return poss[1]; }

}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){

  // set up helper values
  connect.resize(N);
  for( int i = 0; i < M; i++ ){
    connect[ R[i][0] ].pb( mp( R[i][1], L[i] ) );
    connect[ R[i][1] ].pb( mp( R[i][0], L[i] ) );
  }

  if ( M == N-1 ){
    // do my thing -- pyramid explore

    explored.resize(N, false);

    isEnd.resize(N, false);
    for( int i = 0; i < K; i++ ){ isEnd[ P[i] ] = true; }

    return delve(0);

  }
  else{

    int vc[N];
    memset( vc, 0, sizeof vc );

    // recursive backtracking .. ? djkistras from the starting points -- GENIUS
    priority_queue< pair<ll,ll>, vector< pair<ll,ll> >, greater< pair<ll,ll> > > PQ;

    for( int i = 0; i < K; i++ ){ PQ.push( mp( 0, P[i]) ); vc[ P[i] ]++; }

    while ( !PQ.empty() ){

      ll dist = PQ.top().first;
      ll ind = PQ.top().second;

      PQ.pop();

      if ( vc[ind] == 2 ){ continue; } // already solved
      if ( vc[ind] == 0 ){ vc[ind]++; continue; }

      // vc[ind] = 1, which means we are at the second-shortest path atm

      if( ind == 0 ){ return dist; }

      for( int i = 0; i < connect[ind].size(); i++ ){
        if( vc[ connect[ind][i].first ] < 2 ){
          PQ.push( mp( dist+connect[ind][i].second, connect[ind][i].first ) );
        }
      }
    }

    return -1;
  }
}

Compilation message (stderr)

crocodile.cpp: In function 'int delve(int)':
crocodile.cpp:20:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for( int j = 0; j < connect[i].size(); j++ ){
      |                   ~~^~~~~~~~~~~~~~~~~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:80:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |       for( int i = 0; i < connect[ind].size(); i++ ){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11