#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1005];
int timer = 0, st[1005], en[1005], l[1005];
void dfs(int i, int p, int d) {
st[i] = timer;
timer++;
if (d % 2 == 0) {
l[i] = st[i];
}
for (int j : adj[i]) {
if (j == p) {
continue;
}
dfs(j, i, d+1);
}
en[i] = timer;
timer++;
if (d % 2 == 1) {
l[i] = en[i];
}
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
vector<int> labels(n);
timer = 0;
for (int i = 0; i <= n; i++) {
adj[i].clear();
en[i] = 0;
}
int leaf = 0;
for (int i = 0; i < n-1; i++) {
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
for (int i = 0; i < n; i++) {
sort(adj[i].begin(), adj[i].end());
if (adj[i].size() == 1) {
leaf = i;
}
}
dfs(leaf, -1, 0);
vector<int> ind;
for (int i = 0; i < n; i++) {
ind.push_back(l[i]);
}
sort(ind.begin(), ind.end());
for (int i = 0; i < n; i++) {
labels[i] = lower_bound(ind.begin(), ind.end(), l[i]) - ind.begin();
}
return labels;
}
int find_next_station(int s, int t, vector<int> c) {
int ins = -1, outs = -1;
if (c.size() == 1) {
return c.back();
}
if (s == t) {
return s;
}
for (int i : c) {
if (i == t) {
return t;
}
}
if (s == 0) {
vector<int> in(c.size()), out(c.size());
ins = s;
outs = c.back()+1;
for (int i = 0; i < c.size(); i++) {
out[i] = c[i];
if (i == 0) {
in[i] = ins+1;
} else {
in[i] = out[i-1]+1;
}
}
for (int i = 0; i < c.size(); i++) {
if (in[i] < t && t < out[i]) {
return c[i];
}
}
return c.back();
} else {
int inp = -1, outp = -1;
vector<int> in(c.size()-1), out(c.size()-1);
if (s < c.front()) {
inp = s-1;
outp = c.back();
c.pop_back();
ins = s;
outs = c.back()+1;
for (int i = 0; i < c.size(); i++) {
out[i] = c[i];
if (i == 0) {
in[i] = ins+1;
} else {
in[i] = out[i-1]+1;
}
}
for (int i = 0; i < c.size(); i++) {
if (in[i] < t && t < out[i]) {
return c[i];
}
}
return outp;
} else {
inp = c.front();
outp = s+1;
c.erase(c.begin());
ins = c.front()-1;
outs = s;
for (int i = c.size()-1; i >= 0; i--) {
in[i] = c[i];
if (i == c.size()-1) {
out[i] = outs-1;
} else {
out[i] = in[i+1]-1;
}
}
for (int i = 0; i < c.size(); i++) {
if (in[i] < t && t < out[i]) {
return c[i];
}
}
return inp;
}
}
}
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:93:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:101:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
stations.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | if (i == c.size()-1) {
| ~~^~~~~~~~~~~~~
stations.cpp:121:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int i = 0; i < c.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
353 ms |
968 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
251 ms |
684 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
364 ms |
940 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
568 ms |
684 KB |
Output is correct |
2 |
Correct |
445 ms |
684 KB |
Output is correct |
3 |
Incorrect |
382 ms |
684 KB |
Wrong query response. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
407 ms |
940 KB |
Wrong query response. |
2 |
Halted |
0 ms |
0 KB |
- |