# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1257545 | Nurislam | 기지국 (IOI20_stations) | C++20 | 0 ms | 0 KiB |
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u,vector<int> v) {
vector<vector<int>> g(n);
for(int i = 0; i+1 < n; i ++ ) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
};
int ct = 0;
vector<int> l(n);
function<void(int,int,int)> dfs = [&](int ps,int pr, int tp) {
if(tp) l[ps] = ct ++ ;
for(int to : g[ps] )
if(to != pr)
dfs(to,ps,tp^1);
if(!tp) l[ps] = ct ++ ;
};
dfs(0,0,1);
return l;
};
int find_next_station(int s, int t, vector<int> g) {
if(s < g[0]){
if(t >= g.back())return g.back();
if(t < s)return g.back();
return g[lower_bound(g.begin(), g.end(), t) - g.begin()];
}else {
if(t <= g[0])return g[0];
if(t > s) return g[0];
return g[lower_bound(g.begin(), g.end(), t) - g.begin());
};
};