| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 316193 | ScarletS | Stations (IOI20_stations) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int maxn = 1e3;
int tin[maxn],tout[maxn],t;
vector<int> edges[maxn];
vector<pii> temp;
void dfs(int c, int p, bool h)
{
tin[c]=++t;
for (int i : edges[c])
if (i!=p)
dfs(i,c,h^1);
tout[c]=++t;
if (h)
temp.push_back({tout[c],c});
else
temp.push_back({tin[c],c});
}
vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
vector<int> labels(n);
for (int i=0;i<n;++i)
edges[i].clear();
for (int i=0;i<n-1;++i)
{
edges[u[i]].push_back(v[i]);
edges[v[i]].push_back(u[i]);
}
temp.clear();
t=-1;
dfs(0,-1,0);
sort(temp.begin(), temp.end());
for (int i=0;i<n;++i)
labels[temp[i].s]=i;
return labels;
}
int find_next_station(int a, int b, vector<int> c)
{
int x = c.size();
vector<pii> v;
sort(c.begin(), c.end());
if (a==0)
{
v.push_back({1,c[0]});
for (int i=1;i<x;++i)
v.push_back({{c[i-1]+1,c[i]}});
for (pii i : v)
if (i.f<=b&&b<=i.s)
return i.s;
while (1)
++s;
}
if (a<c[0])
{
if (x>1)
{
v.push_back({a+1,c[0]});
if (a+1<=b&&b<=c[0])
return c[0];
for (int i=1;i<x-1;++i)
if (c[i-1]+1<=b&&b<=c[i])
return c[i];
}
return c.back();
}
if (x>1)
{
if (c[x-1]<=b&&b<=a-1)
return c[x-1];
for (int i=x-2;i>=0;--i)
if (c[i]<=b&&b<=c[i+1]-1)
return c[i];
}
return c[0];
}
/**
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin>>n;
return 0;
}**/