# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
319752 | northlake | Stations (IOI20_stations) | C++17 | 0 ms | 0 KiB |
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<stations.h>
#include<bits/sdtc++.h>
using namespace std;
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
// create adjacency list
vector<int> adjacency_list[n] = {};
for (int i = 0; i < n-1; i++) {
int fnode = u[i]; int snode = v[i];
adjacency_list[fnode].push_back(snode); adjacency_list[snode].push_back(fnode);
}
// find origin
int origin;
for (int i = 0; i < n; i++) {
if (adjacency_list[i].size() == 1) {
origin = i;
break;
}
}
// create labels
vector<int> labels(n);
bool visited[n] {false};
int counter = 0;
int current_node = origin;
while (counter < n) {
visited[current_node] = true;
labels[current_node] = counter;
counter += 1;
for (auto neighbor : adjacency_list[current_node]) {
if (!visited[neighbor]) {
current_node = neighbor;
break;
}
}
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
if (t > s) return *max_element(c.begin(), c.end());
else return *min_element(c.begin(), c.end());
}