제출 #1026902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026902		mircea_007	기지국 (IOI20_stations)	C++17	0 / 100	3047 ms	2097152 KiB

stations

#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 ) {
    labels.resize(n);
    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 );

    return 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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 16
• Subtask 4: 0 / 10
• Subtask 5: 0 / 61