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 "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
int tt=0;
vector<int> ans;
vector<vector<int>> adj;
void dfs(int c=0, int p=-1, bool b=0){
if (!b) ans[c] = tt++;
for (auto nxt : adj[c]) if (nxt != p) dfs(nxt, c, b^1);
if (b) ans[c] = tt++;
}
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
ans.assign(n, -1), adj.resize(n);
for (int i = 0; i < n-1; i++)
adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]);
dfs();
return ans;
}
int find_next_station(int s, int t, vector<int> c) {
sort(c.begin(), c.end());
bool b=s>c[0];
for (auto v : c) assert((s>v)==b);
if (b){ //i'm postorder
int p = c[0];
if (sz(c) == 1 || t < c[1] || t > s) //either going out of my subtree, there is no subtree
return p;
int ans=-1;
for (auto nxt : c) if (nxt != p) {
if (nxt <= t) ans = nxt;
}
return ans;
} else { //i'm preorder
int p = c[sz(c)-1];
if (sz(c) == 1 || t < s || t > c[sz(c)-1]) //either going out of my subtree, there is no subtree
return p;
int ans=-1;
for (auto nxt : c) if (nxt != p) {
if (nxt >= t){
ans = nxt;
break;
}
}
return ans;
}
}
# | 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... |