Submission #312000

#	Time	Username	Problem	Language	Result	Execution time	Memory
312000		MrGary	Stations (IOI20_stations)	C++17	0 / 100	919 ms	1128 KiB

stations

/*
{
######################
#       Author       #
#        Gary        #
#        2020        #
######################
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
#include "stations.h"
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
vector<int> g[1001];
int id[1001];
int cnt=0;
void run(int now,int pre=0,int depth=1){
	if(depth) id[now]=cnt++;
	for(auto it:g[now]){
		if(it!=pre){
			run(it,now,depth^1);
		}
	}
	if(!depth) id[now]=cnt++;
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	std::vector<int> labels(n);
	cnt=0;
	rep(i,n)
		g[i].clear();
	rep(i,n-1)
		g[u[i]].PB(v[i]),g[v[i]].PB(u[i]);
	run(0); 
	rep(i,n)
		labels[i]=id[i];
	return labels;
}
int find_next_station(int s, int t, std::vector<int> c) {
	sort(ALL(c));
	if(s<c[0]){
		if(s==0||(c.size()>=2&&t<=c[c.size()-2])){
			return *lower_bound(ALL(c),t);
		}
		return c.back();
	} 
	else{
		if(c.size()>=2&&t>=c[1]){
			return *(upper_bound(ALL(c),t)-1); 
		}
		return c[0];
	}
}
//int main(){
//	fastio;
//	vector<int>v=label(5, 10, {0, 1, 1, 2}, {1, 2, 3, 4});
//	cout<<find_next_station(4,3,{1,3,6})<<endl;
//	for(auto it:v) cout<<it<<' ';
//	cout<<endl;
//	return 0;
//}

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