This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using namespace std;
const int N1 = 1005;
vector<int> nei[N1];
int d[N1];
bool seen[N1];
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 (k == 1e9){
for (int i=0;i<n-1;i++){
lab[u[i]] += (1<<v[i]);
lab[v[i]] += (1<<u[i]);
}
lab[0] += 1e8;
return lab;
}
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 = mn, lb = 0;
while (cur){
int ncur = 0;
lab[cur] = lb++;
seen[cur] = 1;
for (int i : nei[cur])
if (!seen[i])
ncur = i;
cur = ncur;
}
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){
// 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];
// }
bool tt = true, t2 = true;
for (int i=0;i<n;i++){
tt &= lab[i] == i+1;
if (lab[i] > n)
t2 = false;
}
if (tt and lab[0] == 1){
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 (t2){
if (s > t)
return s - 1;
return s + 1;
}
}
Compilation message (stderr)
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:122:1: warning: control reaches end of non-void function [-Wreturn-type]
122 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |