oj.uz

Submission #646844

# Submission time Handle Problem Language Result Execution time Memory
646844 2022-09-30T21:30:43 Z mircea_007 Speedrun (RMI21_speedrun) C++17
100 / 100
 224 ms 720 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 672 KB Output is correct
2 Correct 194 ms 672 KB Output is correct
3 Correct 196 ms 672 KB Output is correct
4 Correct 204 ms 668 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 664 KB Output is correct
2 Correct 134 ms 660 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 708 KB Output is correct
2 Correct 136 ms 672 KB Output is correct
3 Correct 217 ms 684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 680 KB Output is correct
2 Correct 175 ms 672 KB Output is correct
3 Correct 161 ms 672 KB Output is correct
4 Correct 190 ms 684 KB Output is correct
5 Correct 222 ms 672 KB Output is correct
6 Correct 212 ms 720 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 708 KB Output is correct
2 Correct 208 ms 676 KB Output is correct
3 Correct 180 ms 684 KB Output is correct
4 Correct 189 ms 672 KB Output is correct
5 Correct 224 ms 668 KB Output is correct
6 Correct 201 ms 672 KB Output is correct
7 Correct 204 ms 676 KB Output is correct