Submission #1047101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047101		amirhoseinfar1385	Stations (IOI20_stations)	C++17	100 / 100	505 ms	1184 KiB

stations

#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
vector<int>ret;
int n,timea=0,k,high[maxn];
vector<int>adj[maxn];

void dfs(int u,int par=-1){
	timea++;
	if(high[u]&1){
		ret[u]=timea;
	}
	for(auto x:adj[u]){
		if(x!=par){
			high[x]=high[u]^1;
			dfs(x,u);
		}
	}
	timea++;
	if((high[u])==0){
		ret[u]=timea;
	}
}

std::vector<int> label(int n_, int k_, std::vector<int> u, std::vector<int> v) {
	n=n_;
	k=k_;
	timea=-1;
	for(int i=0;i<=n;i++){
		adj[i].clear();
	}
	for(int i=0;i<n-1;i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	high[0]=1;
	ret.clear();
	ret.resize(n);
	dfs(0);
	vector<int>allind;
	for(int i=0;i<n;i++){
		allind.push_back(ret[i]);
	}
	sort(allind.begin(),allind.end());
	for(int i=0;i<n;i++){
		ret[i]=lower_bound(allind.begin(),allind.end(),ret[i])-allind.begin();
	}
	return ret;

}

int find_next_station(int s, int t, std::vector<int> c) {
	vector<int>ch;
	sort(c.begin(),c.end());
	int par=-1;
	if((int)c.size()==1){
		return c[0];
	}
	if(s==0){
		for(int i=0;i<(int)c.size();i++){
			ch.push_back(c[i]);
		}
		int p=lower_bound(ch.begin(),ch.end(),t)-ch.begin();
		return ch[p];
	}else{
		if(s<c[0]){
			par=c.back();
			c.pop_back();
			for(int i=0;i<(int)c.size();i++){
				ch.push_back(c[i]);
			}
			if(!(t>=s&&t<=c.back())){
				return par;
			}
			int p=lower_bound(c.begin(),c.end(),t)-c.begin();
			return c[p];
		}else{
			par=c[0];
			for(int i=1;i<(int)c.size();i++){
				ch.push_back(c[i]);
			}
			if(!(t<=s&&t>=ch[0])){
				return par;
			}
			int p=upper_bound(ch.begin(),ch.end(),t)-ch.begin();
			return ch[p-1];
		}
	}
}

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