#include <bits/stdc++.h>
#include "stations.h"
#define pii pair<int,int>
#define in first
#define out second
#define mp make_pair
using namespace std;
vector<int> label(int n ,int k , vector<int> u , vector<int> v){
vector<int> ans(n) ;
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 tim = 0 ;
vector<int> inn(n) , outt(n), lvl(n) ;
function<void(int,int,int)> dfs = [&](int a, int p, int l){
inn[a]=tim++ ;
lvl[a]=l ;
for(int x :adj[a]){
if(x!=p){
dfs(x,a,l^1) ;
}
}
outt[a]=tim++ ;
};
dfs(0,0,0) ;
for(int i=0;i<n;i++)
ans[i]=(lvl[i]?outt[i]:inn[i]) ;
return ans ;
}
pii get(int x){
return mp(x%(1<<11),(x>>11)) ;
}
bool ancestor(pii s, pii b){
return (s.in<=b.in&&b.out<=s.out);
}
int find_next_station(int s ,int t, vector<int> ne){
int isin = (ne[0]<=s) ;
if(s==0){
for(int i=1;i<ne.size();i++) if(ne[i-1]<t&&t<=ne[i]) return ne[i] ;
return ne[0] ;
}
if(isin^1){
for(int i=1;i+1<ne.size();i++){
if(ne[i]<=t&&t<ne[i+1]){
return ne[i] ;
}
}
if(ne.back()<=t&&t<s) return ne.back() ;
return ne[0] ;
}
for(int i=1;i+1<ne.size();i++){
if(ne[i-1]<t&&t<=ne[i]) return ne[i] ;
}
if(s<=t&&t<=ne[0]) return ne[0] ;
return ne.back() ;
}
/*int main(){
vector<int> u= {0,1,2} , v = {1,2,3} ;
vector<int> res = label(4,1000000,u,v) ;
for(int x : res) cout << x <<" " ;
cout << endl ;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(i!=j){
cout << i << " "<< j << ": " << find_next_station(i,j,adj[i]) << endl ;
}
}
}
return 0 ;
}*/
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=1;i<ne.size();i++) if(ne[i-1]<t&&t<=ne[i]) return ne[i] ;
| ~^~~~~~~~~~
stations.cpp:46:18: 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+1<ne.size();i++){
| ~~~^~~~~~~~~~
stations.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=1;i+1<ne.size();i++){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
408 KB |
Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
534 ms |
612 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1263 ms |
472 KB |
Output is correct |
| 2 |
Incorrect |
854 ms |
500 KB |
Wrong query response. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
595 ms |
656 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
