| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1351510 | jump | 기지국 (IOI20_stations) | C++20 | 0 ms | 0 KiB |
#include "stations.h"
#include <bits/stdc++.h>
int lab=0;
std::vector<int> adj[1010];
std::vector<int> Labels;
void dfs(int curr,int par,bool b){
if(b)Labels[curr]=lab++;
for(auto to:adj[curr]){
if(to==par)continue;
dfs(to,curr,!b);
}
if(!b)Labels[curr]=lab++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
Labels.assign(n,0);
for(int i=0;i<=n;i++)adj.clear();
lab=0;
for(int i=0;i<n-1;i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0,0,0);
//for(auto num:Labels)std::cout << num << ' ';
return Labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
//std::sort(c.begin(),c.end());
bool mi=false;
for(auto num:c){
if(num>s)
mi=true;
if(num==t)return num;
}
if(mi){
if(t>c.back()||t<s)return c[c.size()-1];
int idx = std::upper_bound(c.begin(),c.end(),t)-c.begin();
return c[std::min(idx,(int)(c.size()-1))];
}
else{
if(t<=*c.begin()||t>s)return c[0];
int idx = std::lower_bound(c.begin(),c.end(),t)-c.begin();
return c[std::min(idx,(int)(c.size()-1))];
}
}