Submission #1229935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229935		AlperenT_	Stations (IOI20_stations)	C++20	100 / 100	330 ms	24020 KiB

stations

#include "stations.h"
#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 1e6 + 10 , maxm = 4000 + 10 , maxh = 400 + 10 , lg = 25   , maxk = 100 + 10  , inf = 1e9+ 10 , mod = 1e9 + 9 ;
int cnt =0  , id[maxn];
vector <int> G[maxn] ;
void dfs(int v, int d = 0 , int par =-1){
	if(d==0){
		id[v] = cnt ;cnt++;
	}
	for(int u : G[v]){
		if(u == par)continue ;
		dfs(u , d^1 , v); 
	}
	if(d==1){
		id[v] = cnt ; cnt++ ;
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	rep(i , 0 , n)G[i].clear() ;
	cnt =0 ;
	rep(i , 0 , n-2){
		G[v[i]].pb(u[i]);
		G[u[i]].pb(v[i]); 
	}
	dfs(0,  0);
	vector <int> ans ;
	rep(i , 0 ,n-1)ans.pb(id[i]) ;
	return ans ;
}

int find_next_station(int s, int t, std::vector<int> c) {
	// cout << s << " " << t << " :  " ;
	// for(int x : c)cout << x << " ";
	// cout << "\n"; 
	if(s==0){
		int x = lower_bound(all(c) ,  t) - c.begin() ;
		return c[x]; 
	}
	if(s < c[0]){
		int par = c.back();
		c.pop_back();
		if(sz(c)==0)return par ;
		if(t >= s && t <= c.back()){
			int x= lower_bound(all(c) , t) - c.begin() ;
			return c[x]; 
		}else{
			return par; 
		}
	}else{
		int par = c[0] ;
		vector <int> c2 ;
		rep(i , 1 ,sz(c)-1){
			c2.pb(c[i]) ;
		}
		c=  c2 ;
		if(sz(c) == 0)return par ;
		if(t >= c[0] && t <= s){
			int x =lower_bound(all(c) , t+1) - c.begin()-1 ;
			return c[x] ;
		}else{
			return par ;
		}
	}
	return -1;
}

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