#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
int A[500005],l,in[500005],out[500005],don[500005],mp[500005];
vector <int> v1[500005];
vector <int> labels;
void dfs(int x,int y,int z) {
l++;
in[x]=l;
don[x]=z;
for(int i=0;i<v1[x].size();i++) {
if(v1[x][i]==y) continue;
dfs(v1[x][i],x,z+1);
}
l++;
out[x]=l;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
labels.clear();
labels.resize(n);
for(int i=0;i<n;i++) {
v1[i].clear();
}
l=0;
for(int i=0;i<n-1;i++) {
v1[u[i]].push_back(v[i]);
v1[v[i]].push_back(u[i]);
}
dfs(0,-1,0);
for(int i=0;i<n;i++) {
if(don[i]%2==0) A[i]=in[i];
else A[i]=out[i];
}
sort(A,A+n);
for(int i=0;i<n;i++) {
mp[A[i]]=i;
}
for(int i=0;i<n;i++) {
if(don[i]%2==0) labels[i]=mp[in[i]];
else labels[i]=mp[out[i]];
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
if(s<c[0]) {
for(int i=0;i<c.size()-1;i++) {
if(i==0) {
if(s+1<=t && t<=c[i]) return c[i];
}
else if(c[i-1]+1<=t && t<=c[i]) return c[i];
}
return c[c.size()-1];
}
else {
for(int i=0;i<c.size();i++) {
if(i==c.size()-1) {
if(c[i]<=t && t<=s-1) return c[i];
}
else if(c[i]<=t && t<=c[i+1]-1) return c[i];
}
return c[0];
}
}
Compilation message
stations.cpp: In function 'void dfs(int, int, int)':
stations.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for(int i=0;i<v1[x].size();i++) {
| ~^~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:46:22: 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=0;i<c.size()-1;i++) {
| ~^~~~~~~~~~~
stations.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<c.size();i++) {
| ~^~~~~~~~~
stations.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | if(i==c.size()-1) {
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
583 ms |
24648 KB |
Output is correct |
2 |
Correct |
477 ms |
24508 KB |
Output is correct |
3 |
Correct |
945 ms |
24288 KB |
Output is correct |
4 |
Correct |
745 ms |
24288 KB |
Output is correct |
5 |
Correct |
763 ms |
24288 KB |
Output is correct |
6 |
Correct |
555 ms |
24416 KB |
Output is correct |
7 |
Correct |
598 ms |
24416 KB |
Output is correct |
8 |
Correct |
23 ms |
24528 KB |
Output is correct |
9 |
Correct |
22 ms |
24288 KB |
Output is correct |
10 |
Correct |
18 ms |
24288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
510 ms |
24288 KB |
Output is correct |
2 |
Correct |
613 ms |
24288 KB |
Output is correct |
3 |
Correct |
1073 ms |
24288 KB |
Output is correct |
4 |
Correct |
856 ms |
24568 KB |
Output is correct |
5 |
Correct |
677 ms |
24288 KB |
Output is correct |
6 |
Correct |
491 ms |
24288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
619 ms |
24416 KB |
Output is correct |
2 |
Correct |
598 ms |
24508 KB |
Output is correct |
3 |
Correct |
1016 ms |
24288 KB |
Output is correct |
4 |
Correct |
703 ms |
24288 KB |
Output is correct |
5 |
Correct |
731 ms |
24268 KB |
Output is correct |
6 |
Correct |
547 ms |
24416 KB |
Output is correct |
7 |
Correct |
508 ms |
24420 KB |
Output is correct |
8 |
Correct |
20 ms |
24288 KB |
Output is correct |
9 |
Correct |
20 ms |
24476 KB |
Output is correct |
10 |
Correct |
19 ms |
24288 KB |
Output is correct |
11 |
Correct |
798 ms |
24308 KB |
Output is correct |
12 |
Correct |
562 ms |
24444 KB |
Output is correct |
13 |
Correct |
524 ms |
24416 KB |
Output is correct |
14 |
Correct |
424 ms |
24436 KB |
Output is correct |
15 |
Correct |
72 ms |
24288 KB |
Output is correct |
16 |
Correct |
96 ms |
24288 KB |
Output is correct |
17 |
Correct |
149 ms |
24288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1220 ms |
24288 KB |
Output is correct |
2 |
Correct |
906 ms |
24416 KB |
Output is correct |
3 |
Correct |
907 ms |
24288 KB |
Output is correct |
4 |
Correct |
22 ms |
24288 KB |
Output is correct |
5 |
Correct |
19 ms |
24288 KB |
Output is correct |
6 |
Correct |
20 ms |
24288 KB |
Output is correct |
7 |
Correct |
814 ms |
24288 KB |
Output is correct |
8 |
Correct |
1132 ms |
24288 KB |
Output is correct |
9 |
Correct |
815 ms |
24288 KB |
Output is correct |
10 |
Correct |
607 ms |
24288 KB |
Output is correct |
11 |
Correct |
22 ms |
24288 KB |
Output is correct |
12 |
Correct |
24 ms |
24288 KB |
Output is correct |
13 |
Correct |
23 ms |
24288 KB |
Output is correct |
14 |
Correct |
19 ms |
24288 KB |
Output is correct |
15 |
Correct |
19 ms |
24288 KB |
Output is correct |
16 |
Correct |
683 ms |
24448 KB |
Output is correct |
17 |
Correct |
502 ms |
24288 KB |
Output is correct |
18 |
Correct |
560 ms |
24424 KB |
Output is correct |
19 |
Correct |
624 ms |
24288 KB |
Output is correct |
20 |
Correct |
592 ms |
24288 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
607 ms |
24428 KB |
Output is correct |
2 |
Correct |
510 ms |
24416 KB |
Output is correct |
3 |
Correct |
1043 ms |
24288 KB |
Output is correct |
4 |
Correct |
798 ms |
24288 KB |
Output is correct |
5 |
Correct |
756 ms |
24444 KB |
Output is correct |
6 |
Correct |
511 ms |
24416 KB |
Output is correct |
7 |
Correct |
542 ms |
24288 KB |
Output is correct |
8 |
Correct |
19 ms |
24288 KB |
Output is correct |
9 |
Correct |
22 ms |
24412 KB |
Output is correct |
10 |
Correct |
20 ms |
24288 KB |
Output is correct |
11 |
Correct |
511 ms |
24424 KB |
Output is correct |
12 |
Correct |
681 ms |
24280 KB |
Output is correct |
13 |
Correct |
1029 ms |
24268 KB |
Output is correct |
14 |
Correct |
750 ms |
24300 KB |
Output is correct |
15 |
Correct |
743 ms |
24268 KB |
Output is correct |
16 |
Correct |
540 ms |
24352 KB |
Output is correct |
17 |
Correct |
646 ms |
24268 KB |
Output is correct |
18 |
Correct |
592 ms |
24508 KB |
Output is correct |
19 |
Correct |
610 ms |
24544 KB |
Output is correct |
20 |
Correct |
623 ms |
24288 KB |
Output is correct |
21 |
Correct |
79 ms |
24588 KB |
Output is correct |
22 |
Correct |
102 ms |
24288 KB |
Output is correct |
23 |
Correct |
128 ms |
24444 KB |
Output is correct |
24 |
Correct |
26 ms |
24288 KB |
Output is correct |
25 |
Correct |
20 ms |
24288 KB |
Output is correct |
26 |
Correct |
24 ms |
24444 KB |
Output is correct |
27 |
Correct |
20 ms |
24288 KB |
Output is correct |
28 |
Correct |
19 ms |
24288 KB |
Output is correct |
29 |
Correct |
532 ms |
24268 KB |
Output is correct |
30 |
Correct |
720 ms |
24288 KB |
Output is correct |
31 |
Correct |
552 ms |
24288 KB |
Output is correct |
32 |
Correct |
654 ms |
24288 KB |
Output is correct |
33 |
Correct |
645 ms |
24288 KB |
Output is correct |
34 |
Correct |
359 ms |
24452 KB |
Output is correct |
35 |
Correct |
527 ms |
24508 KB |
Output is correct |
36 |
Correct |
638 ms |
24504 KB |
Output is correct |
37 |
Correct |
587 ms |
24396 KB |
Output is correct |
38 |
Correct |
601 ms |
24508 KB |
Output is correct |
39 |
Correct |
448 ms |
24572 KB |
Output is correct |
40 |
Correct |
559 ms |
24612 KB |
Output is correct |
41 |
Correct |
626 ms |
24668 KB |
Output is correct |
42 |
Correct |
97 ms |
24288 KB |
Output is correct |
43 |
Correct |
157 ms |
24428 KB |
Output is correct |
44 |
Correct |
189 ms |
24288 KB |
Output is correct |
45 |
Correct |
193 ms |
24464 KB |
Output is correct |
46 |
Correct |
385 ms |
24444 KB |
Output is correct |
47 |
Correct |
365 ms |
24288 KB |
Output is correct |
48 |
Correct |
107 ms |
24436 KB |
Output is correct |
49 |
Correct |
83 ms |
24416 KB |
Output is correct |