# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
871420 | andrei_boaca | Stations (IOI20_stations) | C++17 | 564 ms | 1820 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 "stations.h"
#include <bits/stdc++.h>
#include <vector>
//#include "stub.cpp"
using namespace std;
const int baza=1e8;
vector<int> muchii[1005];
int in[1005],out[1005],timp,niv[1005];
bool use[1005];
int n,k;
vector<int> L;
int ch,ind;
int lin[10005];
void dfs(int nod)
{
timp++;
lin[timp]=nod;
in[nod]=timp;
use[nod]=1;
for(int i:muchii[nod])
if(!use[i])
{
niv[i]=niv[nod]+1;
dfs(i);
}
timp++;
lin[timp]=nod;
out[nod]=timp;
}
std::vector<int> label(int N, int K, std::vector<int> u, std::vector<int> v)
{
n=N;
k=K;
L.clear();
L.resize(n);
timp=0;
for(int i=0;i<n;i++)
{
use[i]=0;
muchii[i].clear();
}
for(int i=0;i<u.size();i++)
{
int a=u[i];
int b=v[i];
muchii[a].push_back(b);
muchii[b].push_back(a);
}
niv[0]=1;
dfs(0);
vector<int> ord;
for(int i=1;i<=timp;i++)
{
int nod=lin[i];
if(niv[nod]%2==1)
{
if(in[nod]==i)
ord.push_back(nod);
}
if(niv[nod]%2==0)
{
if(out[nod]==i)
ord.push_back(nod);
}
}
for(int i=0;i<ord.size();i++)
L[ord[i]]=i;
return L;
}
int find_next_station(int s, int t, std::vector<int> c)
{
if(c.size()==1)
return c[0];
if(c[0]>s)
{
for(int i=0;i+1<c.size();i++)
if(s<=t&&t<=c[i])
return c[i];
return c.back();
}
else
{
for(int i=(int)c.size()-1;i>0;i--)
if(c[i]<=t&&t<=s)
return c[i];
return c[0];
}
}
Compilation message (stderr)
# | 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... |