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 <bits/stdc++.h>
#include "stations.h"
using namespace std;
typedef pair <int, int> pii;
vector <int> label(int N, int K, vector <int> u, vector <int> v) {
vector <vector <int>> adj(N);
for (int i = 0; i < N - 1; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
int timer = 0;
vector <pii> sorted;
vector <int> labels(N);
function <void(int, int, int)> dfs = [&](int x, int p, int d) {
int disc = timer++;
for (auto it : adj[x])
if (it != p)
dfs(it, x, d ^ 1);
int fin = timer++;
sorted.push_back({d ? fin : disc, x});
};
dfs(0, -1, 0);
sort(sorted.begin(), sorted.end());
for (int i = 0; i < N; i++)
labels[sorted[i].second] = i;
return labels;
}
int find_next_station(int start, int dest, vector <int> neigh) {
if (start < neigh[0]) {
int parent = neigh.back();
neigh.insert(neigh.begin(), start);
if (start)
neigh.pop_back();
for (int i = 1; i < neigh.size(); i++)
if (dest > neigh[i - 1] && dest <= neigh[i])
return neigh[i];
return parent;
}
else {
int parent = neigh[0];
neigh.erase(neigh.begin());
neigh.push_back(start);
for (int i = 1; i < neigh.size(); i++)
if (dest >= neigh[i - 1] && dest < neigh[i])
return neigh[i - 1];
return parent;
}
}
Compilation message (stderr)
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 1; i < neigh.size(); i++)
| ~~^~~~~~~~~~~~~~
stations.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 1; i < neigh.size(); i++)
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |