| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1199920 | Belphegor | 기지국 (IOI20_stations) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int counter;
vector<int>tree[1005];
vector<int>labels;
void dfs(int cur,int par,int d){
labels[cur] = ++counter;
for(int nxt : tree[cur]){
if(nxt == par) continue;
dfs(nxt,cur,d^1);
}
cout<<cur<<" "<<labels[cur]<<" "<<counter<<'\n';
if(d) labels[cur] = counter;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
labels = vector<int>(n,-1);
counter = -1;
for(int i=0; i<n; i++) tree[i].clear();
for(int i=0; i<u.size(); i++){
int a = u[i],b = v[i];
tree[a].emplace_back(b);
tree[b].emplace_back(a);
}
dfs(0,-1,0);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(c.size() == 1) return c[0];
sort(c.begin(),c.end());
if(c[0] < s){
if(c[1] <= t && t <= s){
c.emplace_back(s);
for(int i=1; i<c.size(); i++){
if(t <= c[i]) return c[i];
}
}
return c[0];
}
else{
int parent = c.back(); c.pop_back();
int p = s;
for(int x : c){
if(p < t && t <= x) return x;
p = x;
}
return parent;
}
}
int main(){
vector<int>s = {0,0,1,1,3};
vector<int>t = {5,1,3,2,4};
for(int x : label(6,1000,s,t)) cout<<x<<" ";
cout<<find_next_station(5,5,{3,5,0});
}