#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define x first
#define y second
vector<int> labels;
vector<vector<int>> g;
int tme;
void dfs1(int i,int f=0,int t=0){
int tin=++tme;
for(auto u:g[i]){
if(u!=f){
dfs1(u,i,(t+1)%2);
}
}
int tout=tme;
if(t==0){
labels[i]=tin*2;
}
else{
labels[i]=tout*2+1;
}
}
// void dfs1(int i, int f=0){
// int tin=++tme;
// for(auto u:g[i]){
// if(u!=f){
// dfs1(u,i);
// }
// }
// int tout=tme;
// labels[i]=tin*1000+tout;
// }
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
tme=-1;
labels.assign(n,-1);
g.assign(n,vector<int>());
for(int i=0; i<n-1; i++){
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
dfs1(0);
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
int r=s%2;
s/=2;
vector<pair<ii,int>> cld;
int f=-1;
if(r==0){
int prev=s;
for(auto i:c){
int k=i/2;
cld.emplace_back(ii(prev+1,k),i);
prev=k;
}
if(s!=0){
f=cld.back().y;
cld.pop_back();
}
}
else{
f=c[0];
for(int j=1; j<c.size(); j++){
int i=c[j];
int k=i/2;
if(!cld.empty())
cld.back().x.y=k-1;
cld.emplace_back(ii(k,-1),i);
}
if(!cld.empty()){
cld.back().x.y=s;
}
}
t/=2;
for(auto i:cld){
if(i.x.x<=t&&i.x.y>=t){
return i.y;
}
}
return f;
}
/*
1
5 100
0 1
1 2
1 3
2 4
3
0 1 2
1 2 2
1 4 2*/
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int j=1; j<c.size(); j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
412 KB |
Invalid labels (duplicates values). scenario=0, label=19 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
320 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1023 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
412 KB |
Invalid labels (duplicates values). scenario=1, label=1727 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
863 ms |
528 KB |
Output is correct |
| 2 |
Correct |
600 ms |
484 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Invalid labels (duplicates values). scenario=1, label=7 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
492 KB |
Invalid labels (duplicates values). scenario=1, label=1995 |
| 2 |
Halted |
0 ms |
0 KB |
- |
