| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 693270 | NemanjaSo2005 | 기지국 (IOI20_stations) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "stations.h"
#define ll long long
using namespace std;
ll N,K,in[1005],out[1005],vrem=0;
vector<ll> stablo[1005],L;
void dfs(ll gde,ll pret){
// cout<<gde<<" dfs "<<pret<<endl;
in[gde]=vrem;
vrem++;
for(int i=0;i<stablo[gde].size();i++)
if(stablo[gde][i]!=pret)
dfs(stablo[gde][i],gde);
out[gde]=vrem;
return;
}
vector<int> label(int n,int k,vector<int> u,vector<int> v){
N=n;
K=k;
for(ll i=0;i<N;i++)
stablo[i].clear();
for(ll i=0;i<N-1;i++){
stablo[u[i]].push_back(v[i]);
stablo[v[i]].push_back(u[i]);
}
vrem=0;
dfs(0,0);
L.clear();
for(ll i=0;i<N;i++){
// cout<<in[i]<<" "<<out[i]<<endl;
L.push_back(in[i]*1000+out[i]);
}
return L;
}
struct slog{
ll in,out;
}niz[1005],tren,tar;
bool isparent(slog a,slog b){
return a.in<=b.in and a.out>=b.out;
}
int find_next_station(int s,int t,vector<int> c){
/*
cout<<s<<" "<<t<<" | ";
for(int i=0;i<c.size();i++)
cout<<c[i]<<" ";
cout<<endl;*/
N=c.size();
for(ll i=0;i<N;i++){
niz[i].in=c[i]/1000;
niz[i].out=c[i]%1000;
}
tar.in=t/1000;
tar.out=t%1000;
tren.in=s/1000;
tren.out=s%1000;/*
cout<<tren.in<<" "<<tren.out<<" "<<tar.in<<" "<<tar.out<<" | ";
for(int i=0;i<c.size();i++)
cout<<niz[i].in<<" "<<niz[i].out<<" ";
cout<<endl;*/
for(ll i=0;i<N;i++)
if(isparent(niz[i],tren)){
swap(niz[i],niz[N-1]);
swap(c[i],c[N-1]);
N--;
break;
}/*
cout<<"BEZ RODITELJA"<<endl;
for(int i=0;i<c.size();i++)
cout<<niz[i].in<<" "<<niz[i].out<<" ";
cout<<endl;*/
for(ll i=0;i<N;i++)
if(isparent(niz[i],tar)){
//cout<<niz[i].in<<" par "<<
return c[i];
}
return c[N];
}