Submission #1221372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221372		CELD_07	Stations (IOI20_stations)	C++20	100 / 100	305 ms	588 KiB

stations

#include "stations.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<ll>> adj;
ll cnt=0, cnt1=0;
vector<ll> in, ou, dist;
vector<int> v1;
inline void dfs(ll n, ll p){
cnt++;
in[n]=cnt;
for(auto y: adj[n]){
if(y!=p){dist[y]=dist[n]+1;dfs(y, n);}
}
cnt++;
ou[n]=cnt;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
vector<vector<ll>>().swap(adj);
vector<int>().swap(v1);
vector<ll>().swap(in);
vector<ll>().swap(ou);
vector<ll>().swap(dist);
dist.assign(n+1, 0);
in.resize(n+1);
ou.resize(n+1);
v1.resize(n);
adj.resize(n+1);
for(int i=0; i<n-1; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
cnt=-1;
dfs(0, 0);
vector<pair<ll, ll>> v2;
for(int i=0; i<n; i++){
if(dist[i]%2==0){
v2.push_back({in[i], i});
}else v2.push_back({ou[i], i});
}
sort(all(v2));
cnt=0;
for(int i=0; i<n; i++){
v1[v2[i].sd]=i;
}
//for(int i=0; i<n; i++)cout<<i<<" "<<v1[i]<<" "<<in[i]<<" "<<ou[i]<<endl;
return v1;
}
int find_next_station(int s, int t, std::vector<int> c){
//cout<<s<<" "<<t<<endl;
ll p, o1=c.size();
if(s==0){
for(int i=0; i<c.size(); i++){
if(t<=c[i])return c[i];
}
}else{
if(c[0]<s){
for(int i=1; i<o1; i++){
if(i!=o1-1 && t<c[i+1] && t>=c[i])return c[i];
if(i==o1-1 && t<s && t>=c[i])return c[i];
}
return c[0];
}else{
for(int i=0; i<o1-1; i++){
if(i!=0 && t>c[i-1] && t<=c[i])return c[i];
if(i==0 && t>s && t<=c[i])return c[i];
}
return c.back();
}
}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
  105 | }
      | ^

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