oj.uz

답안 #911222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911222 2024-01-18T16:08:12 Z contest_alt 철로 (IOI14_rail) C++17
56 / 100
 258 ms 99180 KB 
#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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 1 ms 2676 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2676 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 2908 KB Output is correct
9 Correct 1 ms 2908 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 98724 KB Output is correct
2 Correct 243 ms 98808 KB Output is correct
3 Correct 231 ms 98756 KB Output is correct
4 Correct 234 ms 98900 KB Output is correct
5 Correct 231 ms 98704 KB Output is correct
6 Correct 228 ms 98852 KB Output is correct
7 Correct 233 ms 99180 KB Output is correct
8 Correct 235 ms 98540 KB Output is correct
9 Correct 232 ms 98640 KB Output is correct
10 Correct 240 ms 98640 KB Output is correct

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 98544 KB Output is correct
2 Correct 254 ms 98792 KB Output is correct
3 Correct 235 ms 98640 KB Output is correct
4 Correct 235 ms 98544 KB Output is correct
5 Correct 232 ms 98644 KB Output is correct
6 Correct 239 ms 98704 KB Output is correct
7 Correct 240 ms 98844 KB Output is correct
8 Correct 243 ms 98548 KB Output is correct
9 Correct 235 ms 98644 KB Output is correct
10 Correct 258 ms 98712 KB Output is correct
11 Incorrect 239 ms 98644 KB Output isn't correct
12 Halted 0 ms 0 KB -