# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1168794 | sitablechair | Stations (IOI20_stations) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <algorithm>
#include <vector>
#include "stations.h"
using namespace std;
const int N=100003;
int tdfs=0,tin[N*2],tout[N*2],d[N];
vector<int> big,ans,g[N];
void dfs(int u,int p=0) {
tin[u]=++tdfs;
for(auto v: g[u])
if (v!=p) {
d[v]=d[u]+1;
dfs(v,u);
}
tout[u]=++tdfs;
}
vector<int> label(int n,int k,vector<int> u,vector<int> v) {
ans.resize(n);
For(i,0,n-1) g[i].clear();
big.clear();
tdfs=-1;
For(i,0,n-2) {
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
dfs(0);
//cout << "tin: " << tin[0] << endl;
For(i,0,n-1)
if (d[i]&1) big.pb(tin[i]);
else big.pb(tout[i]);
sort(all(big));
unq(big);
For(i,0,n-1)
if (d[i]&1) {
ans[i]=lower_bound(all(big),tout[i])-big.begin();
}
else {
ans[i]=lower_bound(all(big),tin[i])-big.begin();
//cout << i << " " << tout[i] << endl;
}
return ans;
}
int find_next_station(int s,int t,vector<int> c) {
bool check=1;
sort(all(c));
for(auto u: c) {
//cout << "u: " << u << endl;
if (t==u) return t;
if (u>s) check=0;
}
if (sz(c)==1) return c.back();
if (s==0) {
for(int i=0;i<sz(c);i++) {
int prv=(i==0?1:c[i-1]+1);
if (t<=c[i] && t>=prv) return c[i];
}
}
if (check) {
int mi=*min_element(all(c));
int mi1=2e9;
for(auto u: c)
if (u!=mi && u<mi1) mi1=u;
if (t<s && t>mi1) {
for(int i=0;i<sz(c);i++) {
if (c[i]==mi) continue;
int nxt=(i==sz(c)-1?s:c[i+1]-1);
if (t>=c[i] && t<=nxt) return c[i];
}
} else return mi;
} else {
int ma=*max_element(all(c));
int ma1=-2e9;
for(auto u: c)
if (u!=ma && u>ma1) ma1=u;
if (t>s && t<ma1) {
for(int i=0;i<sz(c);i++) {
if (c[i]==ma) continue;
int prv=(i==0?s+1:c[i-1]+1);
if (t>=prv && t<=c[i]) return c[i];
}
} else return ma;
}
}