#include "stations.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define cout cerr
vector<vector<int>> adjlist;
vector<int> depth;
vector<int> tin;
vector<int> tout;
int tim = 0;
void dfs(int node, int par) {
tin[node] = tim++;
for (int j:adjlist[node]) {
if (j!=par) {
depth[j] = depth[node]+1;
dfs(j,node);
}
}
tout[node] = tim++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
std::vector<int> labels(n);
adjlist=vector<vector<int>>(n);
tin=tout=vector<int>(n,-1);
depth=vector<int>(n,0);
for (int i=0; i<n-1; i++) {
adjlist[u[i]].push_back(v[i]);
adjlist[v[i]].push_back(u[i]);
}
dfs(0,-1);
for (int i = 0; i < n; i++) {
if (depth[i]%2==1) {
labels[i] = tin[i];
}
else {
labels[i] = 1000+tout[i];
}
//cout << i << " " << tin[i] <<" " << tout[i] <<" " << labels[i] << endl;
}
//consider using the euler tour trick on the tree
//for each node, store the left and right times of its subtree in the label (using perfect hashing)
//for a node, you know the tin and tout (call these inv and outv)
//then for every child, you also know the tin and tout of that child (call these inc and outc)
//and the tin and tout of the destination (call these ind and outd)
//so you know that if inv<=ind<=outd<=outv, then the destination is in this subtree
//and if inc<=ind<=outd<=outc for some child, the destination is in the subtree of this child
//if none of these hold, then go up
//this uses at most n^2 labels
//we could just use in but then it jambloats because we don't know where the subtree ends
//actually what about storing out for even depth
//because we know one of the in values for child for free
//and if we know out[node] we know one out value for free
//that should work for 2000
return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
sort(c.begin(), c.end());
//cout << "TRY FIND " << endl;
for (auto i:c) {
//cout << i <<" ";
}
//cout << endl;
//cout << "DOING " << s <<" " << t << endl;
if (t>=1000) {
t-=1000;
}
if (s>=1000) {
//depth is even
s-=1000;
//so all the children are in-values, our node is an out-value
//the lowest in-value is actually the parent, so that can be ignored
c.push_back(s+1);
sort(c.begin(), c.end());
assert(*max_element(c.begin(), c.end())==s+1);
for (int i=2; i<c.size(); i++) {
if (c[i-1]<=t && t<c[i]) {
return c[i-1];
}
}
return c[0];
}
else {
//depth is odd
for (int i=0; i<c.size(); i++) {
c[i]-=1000;
}
//so all the children are out-values, our node is an in-value
//max value is actually the parent
c.push_back(s+1);
sort(c.begin(), c.end());
//assert(c.front()==s+1);
////cout << "DOCTORED C " << endl;
for (auto i:c) {
//cout << i <<" ";
}
//cout << endl;
for (int i=1; i<((int)c.size())-1; i++) {
if (c[i-1]<=t && t<=c[i]) {
return c[i]+1000;
}
}
return c.back()+1000;
}
return c[0];
}
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:15: warning: unused variable 'i' [-Wunused-variable]
68 | for (auto i:c) {
| ^
stations.cpp:84:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i=2; i<c.size(); i++) {
| ~^~~~~~~~~
stations.cpp:93:24: 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:102:19: warning: unused variable 'i' [-Wunused-variable]
102 | for (auto i:c) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=1019 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
344 KB |
Invalid labels (values out of range). scenario=0, k=1000, vertex=0, label=2991 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1192 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
669 ms |
688 KB |
Output is correct |
| 2 |
Correct |
486 ms |
684 KB |
Output is correct |
| 3 |
Correct |
430 ms |
684 KB |
Output is correct |
| 4 |
Correct |
1 ms |
764 KB |
Output is correct |
| 5 |
Correct |
3 ms |
772 KB |
Output is correct |
| 6 |
Correct |
0 ms |
776 KB |
Output is correct |
| 7 |
Correct |
414 ms |
684 KB |
Output is correct |
| 8 |
Correct |
638 ms |
684 KB |
Output is correct |
| 9 |
Correct |
467 ms |
684 KB |
Output is correct |
| 10 |
Correct |
394 ms |
684 KB |
Output is correct |
| 11 |
Correct |
3 ms |
768 KB |
Output is correct |
| 12 |
Correct |
3 ms |
776 KB |
Output is correct |
| 13 |
Correct |
3 ms |
768 KB |
Output is correct |
| 14 |
Correct |
1 ms |
776 KB |
Output is correct |
| 15 |
Correct |
1 ms |
764 KB |
Output is correct |
| 16 |
Correct |
395 ms |
684 KB |
Output is correct |
| 17 |
Correct |
351 ms |
684 KB |
Output is correct |
| 18 |
Correct |
353 ms |
684 KB |
Output is correct |
| 19 |
Correct |
346 ms |
684 KB |
Output is correct |
| 20 |
Correct |
330 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1192 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
