| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1128463 | algoproclub | Stations (IOI20_stations) | C++20 | 0 ms | 0 KiB |
#include "stations.h"
#include <algorithm>
#include <vector>
using namespace std;
vector<vector<int>> g;
vector<int> intime, outtime, depth;
int time;
void dfs(int v) {
intime[v] = time++;
for (int x : g[v])
if (intime[x] == -1) {
depth[x] = depth[v] + 1;
dfs(x);
}
outtime[v] = time++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
g.assign(n, {});
intime.assign(n, -1);
outtime.assign(n, -1);
depth.assign(n, 0);
for (int i = 0; i < n - 1; i++) {
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
time = 0;
dfs(0);
vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = depth[i] % 2 == 0 ? intime[i] / 2 : outtime[i] / 2;
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
// sort(c.begin(), c.end()); they are already sorted
if (s < c[0]) {
// s: intime, c[i]: outtime, c.back(): parent of s
// subtree of s: s < t <= c[c.size() - 2],
// except if s==0 (root), but the below code is correct for it, too
if (t < s || c.size() == 1 || t > c[c.size() - 2])
return c.back();
return *lower_bound(c.begin(), c.end(), t);
} else {
// s: outtime, c[i]: intime, c[0]: parent of s
// subtree of s: c[1] <= t < s
if (t > s || c.size() == 1 || t < c[1])
return c[0];
return *(upper_bound(c.begin(), c.end(), t) - 1);
}
}