#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 s=0){
// int tin=++tme;
// for(auto u:g[i]){
// if(u!=f){
// dfs1(u,i,(t+1)%2,(s+1)%3);
// }
// }
// int tout=tme;
// if(t==0){
// labels[i]=6*tin+3*t+s;
// }
// else{
// labels[i]=6*(tin+tout)+3*t+s;
// }
// }
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);
// for(int i=0; i<n; i++){
// labels[i]=i;
// }
//return labels;
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]);
}
int curr;
for(int i=0; i<n; i++){
if(g[i].size()==1){
curr=i;
}
}
int i=0;
do{
labels[curr]=i++;
if(labels[g[curr][0]]==-1){
curr=g[curr][0];
}
else{
curr=g[curr][1];
}
}while(g[curr].size()>1);
labels[curr]=i;
return labels;
dfs1(0);
return labels;
}
ii get(int x){
return ii(x/3%2,x%3);
}
int find_next_station(int s, int t, std::vector<int> c) {
if(t>s){
return c[0];
}
else{
return c[1];
}
// int tin=t/1000;
// int tout=t%1000;
// int sin=s/1000;
// int sout=s%1000;
// int f;
// for(auto i:c){
// int in=i/1000;
// int out=i%1000;
// if(in<sin){
// f=i;
// continue;
// }
// if (tin>=in&&tout<=out){
// return i;
// }
// }
// return f;
// ii r=get(s);
// s/=6;
// vector<pair<ii,int>> cld;
// int f=-1;
// if(r.x==0){
// int prev=s;
// for(auto i:c){
// if(get(i).y!=(r.y+1)%3){
// f=i;
// continue;
// }
// int k=i/6;
// cld.emplace_back(ii(prev+1,k-(prev+1)),i);
// prev=k-(prev+1);
// }
// }
// else{
// for(auto i:c){
// if(get(i).y!=(r.y+1)%3){
// f=i;
// continue;
// }
// if(!cld.empty())
// cld.back().x.y=i/6-1;
// cld.emplace_back(ii(i/6,-1),i);
// }
// if(!cld.empty()){
// cld.back().x.y=s-(cld[0].x.x-1);
// }
// }
// ii h=get(t);
// t/=6;
// for(auto i:cld){
// if(h.x==0&&i.x.x<=t&&i.x.y>=t){
// return i.y;
// }
// else if(h.x==1&&2*i.x.x<=t&&2*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 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:59:14: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | labels[curr]=i++;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
579 ms |
492 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
280 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=4, label=-1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
567 ms |
520 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
884 ms |
488 KB |
Output is correct |
| 2 |
Incorrect |
653 ms |
400 KB |
Wrong query response. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
545 ms |
528 KB |
Wrong query response. |
| 2 |
Halted |
0 ms |
0 KB |
- |
