Submission #702519

#	Time	Username	Problem	Language	Result	Execution time	Memory
702519		NemanjaSo2005	Stations (IOI20_stations)	C++14	100 / 100	966 ms	840 KiB

stations

#include<bits/stdc++.h>
#include "stations.h"
#define ll long long
using namespace std;
ll N,K,parnost[1005],in[1005],out[1005],vrem=0;
vector<ll> stablo[1005];
vector<int> L;
void dfs(ll gde,ll pret,int par=0){
   in[gde]=++vrem;
   parnost[gde]=par;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         dfs(stablo[gde][i],gde,par^1);
   out[gde]=++vrem;
   return;
}
struct slog{
   int id,sv,nv;
} niz[1005];
bool pov(slog a,slog b){
   return a.sv<b.sv;
}
bool poid(slog a,slog b){
   return a.id<b.id;
}
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();
   //cout<<"LABELE"<<endl;
   for(ll i=0;i<N;i++){
      niz[i].id=i;
      if(parnost[i]==0)
         niz[i].sv=in[i];
      else
         niz[i].sv=out[i];
     // cout<<i<<" "<<L[i]<<endl;
   }
   sort(niz,niz+N,pov);
   for(int i=0;i<N;i++)
      niz[i].nv=i;
   sort(niz,niz+N,poid);
   for(int i=0;i<N;i++)
      L.push_back(niz[i].nv);
   return L;
}

int find_next_station(int s,int t,vector<int> c){
   if(c.size()==1)
      return c[0];
   for(int i=0;i<c.size();i++)
      if(c[i]==t)
         return c[i];
   bool jein=true;
   for(int i=0;i<c.size();i++)
      if(c[i]<s)
         jein=false;
   sort(c.begin(),c.end());
   if(jein){///IN cvor
      if(t<s)
         return c[c.size()-1];
      for(int i=0;i<c.size();i++)
         if(c[i]>=t)
            return c[i];
      return c[c.size()-1];
   }
   ///Out cvor
   if(t>s)
      return c[0];
   for(int i=1;i<c.size();i++)
      if(t<c[i])
         return c[i-1];
   return c[c.size()-1];
}

Compilation message (stderr)

stations.cpp: In function 'void dfs(long long int, long long int, 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++)
      |                ~^~~~~~~~~~~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for(int i=0;i<c.size();i++)
      |                ~^~~~~~~~~
stations.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for(int i=0;i<c.size();i++)
      |                ~^~~~~~~~~
stations.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       for(int i=0;i<c.size();i++)
      |                   ~^~~~~~~~~
stations.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for(int i=1;i<c.size();i++)
      |                ~^~~~~~~~~

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