Submission #835336

#	Time	Username	Problem	Language	Result	Execution time	Memory
835336		welleyth	Stations (IOI20_stations)	C++17	100 / 100	767 ms	1180 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int N = (int)1e3;

int tin[N],tout[N];
int timer = 0;

vector<int> g[N];
int id[N];
int d[N];
int c = 0;
vector<int> labels;

mt19937 rnd(time(nullptr));

int sz[N];
vector<int> values;

void dfs(int v,int pr = -1){
	tin[v] = timer++;
	for(auto& to : g[v]){
		if(to == pr) continue;
		if(id[v] == 0)
			id[to] = ++c;
		else
			id[to] = id[v];
		d[to] = d[v] + 1;
		dfs(to,v);
	}
	tout[v] = timer++;
	if(d[v] % 2 == 0){
		// labels[v] = (tin[v] << 1);
		values.push_back(tin[v]);
	} else {
		// labels[v] = ;
		values.push_back(tout[v]);
	}
	return;
}

void dfs1(int v,int pr = -1){
	sz[v] = 1;
	for(auto& to : g[v]){
		if(to == pr) continue;
		dfs1(to,v);
		sz[v] += sz[to];
	}
	return;
}

int find_centroid(int v,int S){
	for(auto& to : g[v]){
		if(sz[to] > sz[v]) continue;
		if(sz[to] > S/2) return find_centroid(to,S);
	}
	return v;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for(int i = 0; i < n; i++) g[i].clear();
	timer = 0;
	labels.clear();
	labels.resize(n);
	memset(id,0,sizeof id);
	memset(d,0,sizeof d);
	c = 0;
	for(int i = 0; i < n-1; i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs1(0);
	int root = find_centroid(0,n);
	values.clear();
	d[root] = 0;
	dfs(root);
	sort(values.begin(),values.end());
	values.erase(unique(values.begin(),values.end()),values.end());
	for(int i = 0; i < n; i++){
		if(d[i] % 2 == 0){
			labels[i] = lower_bound(values.begin(),values.end(),tin[i]) - values.begin();
		} else {
			labels[i] = lower_bound(values.begin(),values.end(),tout[i]) - values.begin();
		}
	}
	return labels;
}

bool upper(int a,int b){
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int find_next_station(int s, int t, std::vector<int> c) {
	int tinS = 2*N, toutS = -1, tinT = 2*N, toutT = -1;
	bool isToutS = true;
	for(auto& to : c){
		isToutS &= s > to; 
	}
	if(isToutS)
		toutS = s;
	else
		tinS = s;
	tinT = toutT = t;
	int pr = -1;
	for(auto& to : c){
		int in,out;
		if(!isToutS){
			out = to;
			if(pr == -1 || out > pr)
				pr = to;
		}
		else{
			in = to;
			if(pr == -1 || in < pr)
				pr = to;
		}
	}

	int go = -1;

	for(auto& to : c){
		// if(to == pr) continue;
		int in,out;
		if(!isToutS){
			out = to;
			if(tinT < tinS)
				return pr;
			if(out >= tinT && (go == -1 || out < go))
				go = to;
		}
		else{
			in = to;
			if(toutT > toutS)
				return pr;
			if(in <= toutT && (go == -1 || in > go))
				go = to;
		}
	}
	if(go == -1)
		return pr;

	return go;
}

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