# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1080025 | Jawad_Akbar_JJ | Stations (IOI20_stations) | C++17 | 0 ms | 0 KiB |
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];
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){
// }
return lab;
}
int ver;
bool dfs(int u, int s, int t, int p = -1){
if (u == t)
return 1;
for (int i : nei[u]){
if (i == p)
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();
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;
return lab[ver];
}
bool t = true;
for (int i=0;i<n;i++)
t &= lab[i] == i+1;
if (t){
if (lab[s] < lab[t]){
for (int i=1;i<=30;i++)
if ((lab[t]>>i) == lab[s])
return lab[s] * 2 + ((lab[t] & (1<<(i-1))) == 0);
return lab[s] / 2;
}
else{
return lab[s] / 2;
}
}
}