Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stations.h"
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<int>> g;
- vector<int> tin, tout, depth;
- int t;
- void dfs(int node, int parent = -1) {
- if (parent == -1) depth[node] = 0;
- else depth[node] = depth[parent] + 1;
- tin[node] = ++t;
- for (int child : g[node]) {
- if (child != parent) dfs(child, node);
- }
- tout[node] = ++t;
- }
- void compress(vector<int> &v) {
- vector<int> u = v;
- sort(u.begin(), u.end());
- // all values already unique
- for (int &x : v) {
- x = lower_bound(u.begin(), u.end(), x) - u.begin();
- }
- }
- vector<int> label(int n, int k, vector<int> u, vector<int> v) {
- g.clear(), tin.clear(), tout.clear(), depth.clear();
- g.resize(n);
- for (int i = 0; i < u.size(); ++i) {
- g[u[i]].push_back(v[i]);
- g[v[i]].push_back(u[i]);
- }
- t = -1;
- tin.resize(n), tout.resize(n);
- depth.resize(n);
- dfs(0);
- vector<int> labels(n);
- for (int i = 0; i < n; i++) {
- if (depth[i] & 1) labels[i] = tout[i];
- else labels[i] = tin[i];
- }
- compress(labels);
- return labels;
- }
- int find_next_station(int s, int t, vector<int> c) {
- int m = c.size();
- if (m == 1) return c[0];
- sort(c.begin(), c.end());
- if (s < c.front()) { // s has tin, rest have tout
- // c.back() is parent of s
- if (s <= t && t <= c[m-2]) {
- // t is in subtree of s
- // which child
- for (int x : c) {
- if (t <= x) return x;
- }
- } else {
- // t is not in subtree of s
- return c.back();
- }
- } else { // s has tout, rest have tin
- // c.front() is parent of s
- if (c[1] <= t && t <= s) {
- // t is in subtree of s
- // which child
- for (int i = m-1; i >= 0; --i) {
- if (t >= c[i]) return c[i];
- }
- } else {
- // t is not in subtree of s
- return c.front();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement