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;
void dfs(int x, int p, vector < vector < int > > &adj, vector < int > &in, vector < int > &out, vector < int > &labels, int depth) {
static int timer = -1;
in[x] = ++timer;
for(int to : adj[x]) {
if(to != p) {
dfs(to, x, adj, in, out, labels, depth ^ 1);
}
}
out[x] = ++timer;
if(depth) {
labels[x] = in[x];
} else {
labels[x] = out[x];
}
}
vector < int > label(int n, int k, vector < int > u, vector < int > v) {
vector < int > labels(n), in(n), out(n);
vector< vector < int > > adj(n, vector < int >());
for(int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0, -1, adj, in, out, labels, 0);
// vector < vector < int > > g;
// for(int i = 0; i < n; ++i) {
// g.push_back({in[i], i, 1});
// g.push_back({out[i], i, 2});
// }
// sort(g.begin(), g.end());
// for(int cnt = -1, i = 0; i < g.size(); ++i) {
// if(i == 0 || g[i][0] != g[i - 1][0]) ++cnt;
// if(g[i][2] == 1) in[g[i][1]] = cnt;
// if(g[i][2] == 2) out[g[i][1]] = cnt;
// }
return labels;
}
int find_next_station(int s, int t, vector < int > c) {
if(c.size() == 1) return c[0];
sort(c.begin(), c.end());
if(s == 0) {
int my_in = 0;
int my_out = c.back();
for(int i = 0; i < c.size(); ++i) {
int cur_in, cur_out;
if(i == 0) {
cur_in = my_in;
} else {
cur_in = c[i - 1] + 1;
}
cur_out = c[i];
if(cur_in <= t && t <= cur_out) {
return c[i];
}
}
} else {
int my_in = -1, my_out = -1;
if(s < c[0]) {
my_in = s;
my_out = c[(int)c.size() - 2];
for(int i = 0; i < (int)c.size() - 1; ++i) {
int cur_in, cur_out;
cur_out = c[i];
if(i == 0) {
cur_in = my_in;
} else {
cur_in = c[i - 1] + 1;
}
if(cur_in <= t && t <= cur_out) return c[i];
}
return c.back();
} else {
my_in = c[1];
my_out = s;
for(int i = 1; i < (int)c.size(); ++i) {
int cur_in, cur_out;
cur_in = c[i];
if(i == (int)c.size() - 1) {
cur_out = s;
} else {
cur_out = c[i + 1] - 1;
}
if(cur_in <= t && t <= cur_out) return c[i];
}
return c[0];
}
}
}
// int main() {
// vector < int > x = label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
// // for(int i : x) cout << i << ' ';
// cout << find_next_station(3, 9, {5}) << '\n';
// }
Compilation message (stderr)
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i = 0; i < c.size(); ++i) {
| ~~^~~~~~~~~~
stations.cpp:46:10: warning: unused variable 'my_out' [-Wunused-variable]
46 | int my_out = c.back();
| ^~~~~~
stations.cpp:60:22: warning: variable 'my_out' set but not used [-Wunused-but-set-variable]
60 | int my_in = -1, my_out = -1;
| ^~~~~~
stations.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
91 | }
| ^
# | 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... |