#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#include <vector>
const int N = 1005;
struct Edge {
int next, t;
}e[N << 1];
int head[N], edc;
void Add(int x, int y) {
e[++edc] = { head[x], y };
head[x] = edc;
}
int f[20][N], dep[N];
void Dfs(int x) {
dep[x] = dep[f[0][x]] + 1;
for (int i = 0; (1 << i + 1) <= dep[x]; ++i)
f[i + 1][x] = f[i][f[i][x]];
for (int i = head[x]; i; i = e[i].next) {
int y = e[i].t;
if (y == f[0][x]) continue;
f[0][y] = x;
Dfs(y);
}
}
int Lca(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
for (int k = dep[x] - dep[y], i = 0; k; k >>= 1, ++i)
if (k & 1) x = f[i][x];
if (x == y) return x;
for (int i = 19; i >= 0; --i)
if (f[i][x] != f[i][y])
x = f[i][x], y = f[i][y];
return f[0][x];
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
for (int i = 0; i < n; i++) {
labels[i] = i;
}
for (int i = 0; i < n - 1; i++) {
u[i]--; v[i]--;
Add(u[i], v[i]);
Add(v[i], u[i]);
}
Dfs(0);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
//checking for direct link in logn
auto it = lower_bound(c.begin(), c.end(), t);
if (it != c.end() && c[it - c.begin()] == t) return t;
/*
move up from u to lca(u,v) until lca(u,v)==u
if v is lower: move to v by moving towards lca(next,v)=next
else lca(u,v) is v: just move up such that depth[next]==depth[u]-1
*/
int save = Lca(s, t);
if (save != t && save != s) {//different node just move towards it
for (int i = 0; i < c.size(); i++) {
if (dep[c[i]] < dep[s])//move upwards
{
return c[i];
}
}
}
else if (save == s) {//now reached lca(u,v) and u is heigher, move down to v
for (int i = 0; i < c.size(); i++) {
if (Lca(c[i], t) == c[i] && dep[c[i]] > dep[s]) {
return c[i];
}
}
}
else if(save==t){//t is heigher
for (int i = 0; i < c.size(); i++) {
if (Lca(c[i], s) == c[i] && dep[c[i]] > dep[t]) {
return c[i];
}
}
}
}
Compilation message
stations.cpp: In function 'void Dfs(int)':
stations.cpp:30:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
30 | for (int i = 0; (1 << i + 1) <= dep[x]; ++i)
| ~~^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:90:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:96:1: warning: control reaches end of non-void function [-Wreturn-type]
96 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3135 ms |
2012048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
275 ms |
484 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3013 ms |
2097152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
933 ms |
544 KB |
Output is correct |
| 2 |
Execution timed out |
3132 ms |
2071528 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3119 ms |
1892012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
