Submission #646844

#	Time	Username	Problem	Language	Result	Execution time	Memory
646844		mircea_007	Speedrun (RMI21_speedrun)	C++17	100 / 100	224 ms	720 KiB

speedrun

#include <stdio.h> // debug
#include "speedrun.h"

#include <vector>

#define magic_sauce inline __attribute__((always_inline))

using vi = std::vector<int>;

// part 1

vi *adj;
int *par;
int *pre;
int sp;

void dfs1( int u ){
  pre[sp++] = u;
  for( int v : adj[u] )
    if( v != par[u] ){
      par[v] = u;
      dfs1( v );
    }
}

void assignHints( int subtask, int N, int A[], int B[] ){
  int i, j;
  
  setHintLen( 20 );
  
  adj = new vi[N];
  par = new int[N];
  pre = new int[N];
  sp = 0;

  for( i = 1 ; i < N ; i++ ){
    adj[A[i] - 1].push_back(B[i] - 1);
    adj[B[i] - 1].push_back(A[i] - 1);
  }

  par[0] = 0;
  dfs1( 0 );

  for( i = 0 ; i < N ; i++ )
    for( j = 0 ; j < 10 ; j++ )
      setHint( i + 1, j + 1, (par[i] >> j) & 1 );

  for( i = 0 ; i < N - 1 ; i++ )
    for( j = 0 ; j < 10 ; j++ )
      setHint( pre[i] + 1, 11 + j, ((pre[i + 1] >> j) & 1) );

  delete []adj;
  delete []par;
  delete []pre;
}

// part 2

magic_sauce int getPar(){
  int ret = 0;
  for( int i = 0 ; i < 10 ; i++ )
    ret += (getHint( i + 1 ) << i);

  return ret;
}

magic_sauce int getNext(){
  int ret = 0;
  for( int i = 0 ; i < 10 ; i++ )
    ret += (getHint( i + 11 ) << i);

  return ret;
}

void speedrun( int subtask, int N, int start ){
  int u, i, next;
  
  getLength(); // == 20 :O

  u = start - 1;
  while( u )
    goTo( 1 + (u = getPar()) );

  u = 0;
  for( i = N-1 ; i-- ; ){
    next = getNext();
    //printf( "u = %d | next = %d\n", u, next );
    while( !goTo( 1 + next ) ){
      goTo( 1 + (u = getPar()) );
      //printf( "(Fail) u = %d | next = %d\n", u, next );
    }

    u = next;
  }
}

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40