Submission #911222

#	Time	Username	Problem	Language	Result	Execution time	Memory
911222		contest_alt	Rail (IOI14_rail)	C++17	56 / 100	258 ms	99180 KiB

rail

#include "rail.h"

#include <vector>

const int MAXN = 5000;

struct Solver {
  int n;
  int first;
  int *loc;
  int *stype;

  int dist[MAXN][MAXN];
  int nearest[MAXN];
  std::vector<int> adj[MAXN];

  void pass_param( int _n, int _first, int *_loc, int *_stype ) {
    n = _n;
    first = _first;
    loc = _loc;
    stype = _stype;

    for( int i = 0 ; i < n ; i++ )
      stype[i] = 0;

    // precalc
    for( int i = 0 ; i < n ; i++ ){
      for( int j = i + 1 ; j < n ; j++ )
        dist[i][j] = dist[j][i] = getDistance( i, j );
      dist[i][i] = 0;
    }

    for( int i = 0 ; i < n ; i++ ){
      nearest[i] = i > 0 ? 0 : 1;
      for( int j = 0 ; j < n ; j++ )
        if( j != i && dist[i][j] < dist[i][nearest[i]] )
          nearest[i] = j;

      adj[nearest[i]].push_back( i );
      adj[i].push_back( nearest[i] );
    }
  }

  void set_type( int i, int type ) {
    stype[i] = type;

    for( int j : adj[i] )
      if( !stype[j] ){
        int delta = dist[i][j];

        if( type == 1 )
          loc[j] = loc[i] + delta; // C
        else
          loc[j] = loc[i] - delta; // D
        
        set_type( j, 1 + 2 - type );
      }
  }

  int find_left( int C ){
    int D = nearest[C]; // nearest D

    // we want the nearest station to the left of y and not yet coloured
    int mindist = 1e9, station = -1;

    for( int i = 0 ; i < n ; i++ ){
      if( stype[i] )
        continue;

      if( dist[C][i] != dist[C][D] + dist[D][i] )
        continue;

      if( dist[D][i] < mindist ){
        mindist = dist[D][i];
        station = i;
      }
    }

    if( station == -1 )
      return C;

    // ------------station(C)------C---------D----------

    loc[station] = loc[C] - (mindist - dist[D][C]);
    set_type( station, 1 );

    return find_left( station );
  }

  int find_right( int D ){
    int C = nearest[D]; // nearest C

    int mindist = 1e9, station = -1;

    for( int i = 0 ; i < n ; i++ ){
      if( stype[i] )
        continue;

      if( dist[D][i] != dist[D][C] + dist[C][i] )
        continue;

      if( dist[C][i] < mindist ){
        mindist = dist[C][i];
        station = i;
      }
    }

    if( station == -1 )
      return D;

    // ------C------D------station(D)-----------

    loc[station] = loc[D] + (mindist - dist[C][D]);
    set_type( station, 2 );

    return find_right( station );
  }

  void solve() {
    loc[0] = first;
    set_type( 0, 1 );

    int left, right;

    {
      left = 0;
      for( int i = 0 ; i < n ; i++ )
        if( stype[i] == 1 && loc[i] < loc[left] )
          left = i;

      left = find_left( left );
    }

    {
      right = nearest[0];
      for( int i = 0 ; i < n ; i++ )
        if( stype[i] == 2 && loc[i] > loc[right] )
          right = i;

      right = find_right( right );
    }

    // for( int i = 0 ; i < n ; i++ )
    //   if( !stype[i] )
    //     printf( "COAIE!\n" );
  }
} solver;

void findLocation( int N, int first, int location[], int stype[] ) {
  solver.pass_param( N, first, location, stype );
  solver.solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 22 / 22
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44