# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
563781 | Leo121 | 기지국 (IOI20_stations) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "stations.h"
#include <bits/stdc++.h>
#include <vector>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) for(int i = 0; i < int(n); ++ i)
#define for1(i, n) for(int i = 1; i <= int(n); ++ i)
#define pb push_back
using namespace std;
typedef vector<int> vi;
const int maxn = 1e3;
vi tree[maxn];
vi num;
int cnt;
void dfs(int u, int p, bool aux){
if(!aux){
num[u] = ++ cnt;
}
for(auto v : tree[u]){
if(v == p){
continue;
}
dfs(v, u, aux ^ 1);
mayor[u] = mayor[v];
}
if(aux){
num[u] = ++ cnt;
}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
num.clear();
num.resize(n);
for0(i, maxn){
tree[i].clear();
}
for0(i, n - 1){
tree[u[i]].pb(v[i]);
tree[v[i]].pb(u[i]);
}
cnt = -1;
dfs(0, 0, 0);
return num;
}
int find_next_station(int s, int t, std::vector<int> c) {
if((int) c.size() == 1){
return c[0];
}
int li = 1, ls = c.size() - 1, mitad;
if(!s){
while(li <= ls){
mitad = (li + ls) / 2;
if(t > c[mitad - 1] && t <= c[mitad]){
return c[mitad];
}
if(t > c[mitad]){
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
return c[0];
}
if(s > c[0]){
ls --;
while(li <= ls){
mitad = (li + ls) / 2;
if(t >= c[mitad] && t < c[mitad + 1]){
return c[mitad];
}
if(t > c[mitad]){
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
return (t >= c[(int) c.size() - 1] && t < s) ? c[(int) c.size() - 1] : c[0];
}
ls --;
while(li <= ls){
mitad = (li + ls) / 2;
if(t <= c[mitad] && t > c[mitad - 1]){
return c[mitad];
}
if(t > c[mitad]){
li = mitad + 1;
}
else{
ls = mitad - 1;
}
}
return (t <= c[0] && t > s) ? c[0] : c[(int) c.size() - 1];
}