| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 321817 | lukameladze | 기지국 (IOI20_stations) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "stations.h"
# include <bits/stdc++.h>
using namespace std;
long long lv[300005],tin,out[300005],in[300005],x[300005],tout;
std::vector <long long> v1[300005];
std::vector <int> labels;
vector < pair <long long, long long> >v2;
void dfs(int a, int p)
{
lv[a]=lv[p]+1;
tin++;
in[a]=tin;
for (int i=0; i<v1[a].size(); i++)
{
if (p!=v1[a][i])
{
dfs(v1[a][i],a);
}
}
tin++;
out[a]=tin;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
{
for (int i=0; i<n-1; i++)
{
v1[u[i]].push_back(v[i]);
v1[v[i]].push_back(u[i]);
}
dfs(0,-1);
for (int i=0; i<n; i++)
{
if (lv[i]%2==1)
{
x[i]=in[i];
}
else x[i]=out[i];
v2.push_back({x[i],i});
}
sort(v2.begin(), v2.end());
for (int i=0; i<v2.size(); i++)
{
labels[v2[i].second]=i;
}
return labels;
}
int find_next_station(int s, int t, std::vector<int> c )
{
if (c[0]<s)
{
for (int i=1; i<c.size()-1; i++)
{
tin=c[i];
tout=c[i+1]-1;
if (tin>=t && tout<=t) return c[i];
}
tin=c[c.size()-1];
tout=s-1;
if (tin>=t && tout<=t) return c[c.size()-1];
return c[0];
}
else
{
tin=s+1;
tout=c[0];
if (tin>=t && tout<=t) return c[0];
for (int i=1; i<c.size()-1; i++)
{
tin=c[i-1]+1;
tout=c[i];
if (tin>=t && tout<=t) return c[i];
}
return c[c.size()-1];
}
}