#include "stations.h" #include <vector> #include <algorithm> #define vec vector #define For(i, n) for(int i = 0; i < n; i++) using namespace std; void dfs(int x, vec<int>&odp, vec<vec<int>>&g, int &et, int typ, int pr = -1){ if(typ == 1) { odp[x] = et; et++; } for(auto &i : g[x]){ if(i == pr) continue; dfs(i, odp, g, et, 1 - typ, x); } if(typ == 0) { odp[x] = et; et++; } return; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { vec<int> odp(n); vec<vec<int>> g(n); For(i, u.size()){ g[u[i]].push_back(v[i]); g[v[i]].push_back(u[i]); } int et = 0; dfs(0, odp, g, et, 0); return odp; } int find_next_station(int s, int t, std::vector<int> c) { vec<int> p; if(c[0] > s){ int maxi = s; if(c.size() >= 2) maxi = c[c.size()-2]; if(t < s || t > maxi) return c.back(); int qq = lower_bound(c.begin(), c.end(), t) - c.begin(); return c[qq]; } else{ int mini = s; if(c.size() >= 2) mini = c[1]; if(t < mini || t > s) return c[0]; c.push_back(s); int qq = upper_bound(c.begin(), c.end(), t) - c.begin() - 1; return c[qq]; } return -1; }