Submission #693276

#	Time	Username	Problem	Language	Result	Execution time	Memory
693276		NemanjaSo2005	Stations (IOI20_stations)	C++14	52.32 / 100	848 ms	908 KiB

stations

#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];
vector<int> L;
void dfs(ll gde,ll pret){
  // cout<<gde<<" dfs "<<pret<<endl;
   in[gde]=++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);
   for(int i=0;i<N;i++){
      in[i]--;
      out[i]--;
   }
   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];
}

Compilation message (stderr)

stations.cpp: In function 'void dfs(long long int, long long int)':
stations.cpp:11:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |    for(int i=0;i<stablo[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 16 / 16
• Subtask 4: 10 / 10
• Subtask 5: 26.3205 / 61