# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1026905 | mircea_007 | 기지국 (IOI20_stations) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 );
}