oj.uz

Submission #552272

# Submission time Handle Problem Language Result Execution time Memory
552272 2022-04-23T01:28:01 Z QuantumK9 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 482 ms 75064 KB 
#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; }

      vc[ind] = 2;

      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

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:82: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]
   82 |       for( int i = 0; i < connect[ind].size(); i++ ){
      |                       ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 444 KB Output is correct
12 Correct 5 ms 1108 KB Output is correct
13 Correct 3 ms 832 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 444 KB Output is correct
12 Correct 5 ms 1108 KB Output is correct
13 Correct 3 ms 832 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 454 ms 71092 KB Output is correct
17 Correct 68 ms 13256 KB Output is correct
18 Correct 77 ms 14812 KB Output is correct
19 Correct 482 ms 75064 KB Output is correct
20 Correct 244 ms 47244 KB Output is correct
21 Correct 35 ms 5868 KB Output is correct
22 Correct 412 ms 44788 KB Output is correct