oj.uz

Submission #1026908

# Submission time Handle Problem Language Result Execution time Memory
1026908 2024-07-18T13:23:48 Z mircea_007 Stations (IOI20_stations) C++17
0 / 100
 626 ms 936 KB 
#include "stations.h"

#include <vector>
#include <algorithm>

struct Solver {
  std::vector<std::vector<int>> adj;
  std::vector<int> *labels;
  int time = 0;

  void dfs( int u, int p, bool parity = false ) {
    if( parity == false )
      (*labels)[u] = time++;

    for( int v : adj[u] )
      if( v != p )
        dfs( v, u, !parity );

    if( parity == true )
      (*labels)[u] = time++;
  }

  std::vector<int> gen_labels( int n, int k, std::vector<int> u, std::vector<int> v ) {
    std::vector<int> loc_labels(n);
    labels = &loc_labels;

    adj.resize(n);

    for( int i = 0; i < n - 1; i++ ){
      adj[u[i]].push_back( v[i] );
      adj[v[i]].push_back( u[i] );
    }

    time = 0;
    dfs( 0, 0 );
    adj.clear();

    return loc_labels;
  }

  int query( int src, int dest, std::vector<int> c ) {
    int min_c = 1e9, max_c = -1e9;
    for( int val : c ) {
      min_c = std::min( min_c, val );
      max_c = std::max( max_c, val );
    }

    int has_par = !!src;

    if( src < min_c ){
      int last_child = c[(int)c.size() - 1 - has_par];
      if( dest < src || dest > last_child )
        return c.back(); // parent

      int idx = 0;
      while( c[idx] < dest )
        idx++;

      return c[idx];
    }else{
      int last_child = c[has_par];
      if( dest > src || dest < last_child )
        return c.front(); // parent

      int idx = (int)c.size() - 1;
      while( c[idx] > dest )
        idx--;

      return c[idx];
    }
  }
} solver;

std::vector<int> label( int n, int k, std::vector<int> u, std::vector<int> v ){
  return solver.gen_labels( n, k, u, v );
}

int find_next_station( int s, int t, std::vector<int> c ){
  return solver.query( s, t, c );
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 301 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 326 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 684 KB Output is correct
2 Correct 456 ms 936 KB Output is correct
3 Incorrect 387 ms 684 KB Wrong query response.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 377 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -