#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 "stations.h"
#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++) {
Add(u[i], v[i]);
Add(v[i], u[i]);
}
Dfs(1);
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] && Lca(c[i],t)==save)//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];
}
}
}
}
/*
#include <cstdio>
#include <cassert>
#include <map>
#include <vector>
#include <algorithm>
static int max_label = 0;
static int r, n, k, q;
static std::vector<int> u, v, labels, answers;
static std::map<int, int> reverse_labels;
static std::vector<std::vector<int>> adjlist;
static int s, t, w;
static std::vector<int> c;
int main() {
cin >> r;
for (int tc = 0; tc < r; tc++) {
cin >> n >> k;
u.resize(n - 1);
v.resize(n - 1);
adjlist.clear();
adjlist.resize(n);
for (int i = 0; i < n - 1; i++) {
cin >> u[i] >> v[i];
adjlist[u[i]].push_back(v[i]);
adjlist[v[i]].push_back(u[i]);
}
labels = label(n, k, u, v);
if ((int)labels.size() != n) {
printf("Number of labels not equal to %d\n", n);
exit(0);
}
reverse_labels.clear();
for (int i = 0; i < n; i++) {
if (labels[i] < 0 || labels[i] > k) {
printf("Label not in range 0 to %d\n", k);
exit(0);
}
if (reverse_labels.find(labels[i]) != reverse_labels.end()) {
printf("Labels not unique\n");
exit(0);
}
reverse_labels[labels[i]] = i;
if (labels[i] > max_label) {
max_label = labels[i];
}
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> s >> t >> w;
c.clear();
for (int v : adjlist[s]) {
c.push_back(labels[v]);
}
std::sort(c.begin(), c.end());
int answer = find_next_station(labels[s], labels[t], c);
if (!std::binary_search(c.begin(), c.end(), answer)) {
printf("Label %d returned by find_next_station not found in c\n", answer);
exit(0);
}
answers.push_back(reverse_labels[answer]);
}
}
printf("%d\n", max_label);
for (int index : answers) {
printf("%d\n", index);
}
exit(0);
}*/
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:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:95:1: warning: control reaches end of non-void function [-Wreturn-type]
95 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3109 ms |
1612208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3123 ms |
1814432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1015 ms |
512 KB |
Output is correct |
| 2 |
Runtime error |
2915 ms |
2097152 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2888 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
