# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
305533 | JustInCase | Stations (IOI20_stations) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "stations.h"
#include <vector>
#include <iostream>
#define int32_t int
#define int64_t long long
const int32_t MAX_N = 1000;
struct Vertex {
int32_t label;
std::vector< int32_t > v;
};
Vertex g[MAX_N + 5];
void dfs(int32_t u, int32_t &t, int32_t par, int32_t dep) {
if(dep % 2 == 0) {
g[u].label = t++;
}
for(auto &v : g[u].v) {
if(v != par) {
dfs(v, t, u, dep + 1);
}
}
if(dep % 2 != 0) {
g[u].label = t++;
}
}
std::vector< int32_t > label(int32_t n, int32_t k, std::vector< int32_t > u, std::vector< int32_t > v) {
for(int32_t i = 0; i < n; i++) {
g[i].v.clear();
}
for(int32_t i = 0; i < n - 1; i++) {
g[u[i]].v.push_back(v[i]);
g[v[i]].v.push_back(u[i]);
}
int32_t t = 0;
dfs(0, t, -1, 0);
std::vector< int32_t > labels(n);
for(int32_t i = 0; i < n; i++) {
labels[i] = g[i].label;
}
return labels;
}
int32_t find_next_station(int32_t s, int32_t t, std::vector< int32_t > c) {
if(s < c[0]) {
if(t > c[c.size() - 2]) {
return c[c.size() - 1];
}
if(t < s) {
return c[c.size() - 1];
}
else {
return *std::lower_bound(c.begin(), c.end(), t);
}
}
else {
if(t <= c[0]) {
return c[0];
}
else if(t > s) {
return c[0];
}
else {
return *--std::upper_bound(c.begin(), c.end(), t);
}
}
}