#include <iostream>
#include <vector>
using namespace std;
const int N1 = 1005;
vector<int> nei[N1];
int d[N1], num[N1];
bool seen[N1];
void dfs1(int u, int p = -1, int cur = 0){
num[u] = cur;
for (int i : nei[u])
if (i != p)
dfs1(i, u, cur+1);
}
vector<int> label(int n, int k, vector<int> u, vector<int> v){
bool t = 1;
for (int i=0;i<n-1;i++){
nei[u[i]].push_back(v[i]);
nei[v[i]].push_back(u[i]);
d[u[i]]++;
d[v[i]]++;
t &= min(u[i], v[i]) == i / 2;
t &= max(u[i], v[i]) == i+1;
}
vector<int> lab(n, 0);
if (t){
for (int i=0;i<n;i++)
lab[i] = i + 1;
return lab;
}
int mx = 0, mn = 0;
for (int i=0;i<n;i++){
if (d[i] > d[mx])
mx = i;
if (d[i] < d[mn])
mn = i;
}
if (d[mx] <= 2){
int cur;
for (int i=0;i<n;i++)
if (d[i] == 1)
cur = i;
dfs1(cur);
for (int i=0;i<n;i++)
lab[i] = num[i];
return lab;
}
return lab;
}
int ver;
bool dfs(int u, int s, int t, int p = -1){
if (u == t)
return 1;
seen[u] = 1;
for (int i : nei[u]){
if (seen[i])
continue;
bool b = dfs(i, s, t, u);
if (b and u == s)
ver = i;
if (b)
return 1;
}
return 0;
}
int find_next_station(int s, int t, vector<int> lab){
int n = lab.size();
for (int i=0;i<n;i++)
nei[i].clear(), seen[i] = 0;
// if (lab[0] > 1e8){
// for (int i=0;i<n;i++)
// if (lab[i] == s){
// s = i;
// break;
// }
// for (int i=0;i<n;i++)
// if (lab[i] == t){
// t = i;
// break;
// }
// lab[0] -= 1e8;
// for (int i=0;i<n;i++){
// for (int j=0;j<n;j++)
// if ((1<<j) & lab[i])
// nei[i].push_back(j);
// }
// lab[0] += 1e8;
// ver = -1;
// bool b = dfs(s, s, t);
// if (ver == -1)
// return lab[0];
// return lab[ver];
// }
if (lab.size() == 1)
return lab[0];
bool tt = 1;
for (int i : lab)
tt &= (i == s * 2 or i == s * 2 + 1 or i == s / 2);
if (tt){
if (s < t){
for (int i=1;i<=30;i++)
if ((t>>i) == s)
return (t >> (i-1));
return s / 2;
}
else{
return s / 2;
}
}
if (lab.size() == 2){
if (s > t)
return s - 1;
return s + 1;
}
}
Compilation message
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
132 | }
| ^
stations.cpp: In function 'std::vector<int> label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:49:7: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
49 | dfs1(cur);
| ~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Invalid labels (duplicates values). scenario=1, label=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
361 ms |
940 KB |
Output is correct |
| 2 |
Correct |
392 ms |
688 KB |
Output is correct |
| 3 |
Correct |
535 ms |
684 KB |
Output is correct |
| 4 |
Correct |
449 ms |
684 KB |
Output is correct |
| 5 |
Correct |
395 ms |
684 KB |
Output is correct |
| 6 |
Correct |
313 ms |
684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Invalid labels (duplicates values). scenario=1, label=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
590 ms |
684 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Invalid labels (duplicates values). scenario=2, label=0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Invalid labels (duplicates values). scenario=1, label=0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
