Submission #835215

#	Time	Username	Problem	Language	Result	Execution time	Memory
835215		welleyth	Stations (IOI20_stations)	C++17	73.36 / 100	801 ms	944 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));

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);
	} else {
		labels[v] = (tout[v] << 1) | 1;
	}
	return;
}

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]);
	}
	int root = 0;
	for(int i = 0; i < n; i++) if(g[i].size() > g[root].size()) root = i;
	root = rnd()%n;
	d[root] = -1;
	dfs(root);
	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;
	if(s & 1)
		toutS = s >> 1;
	else
		tinS = s >> 1;
	if(t & 1)
		toutT = t >> 1;
	else
		tinT = t >> 1;
	int pr = -1;
	for(auto& to : c){
		int in,out;
		if(to & 1){
			out = to >> 1;
			if(pr == -1 || out > (pr >> 1))
				pr = to;
		}
		else{
			in = to >> 1;
			if(pr == -1 || in < (pr >> 1))
				pr = to;
		}
	}

	int go = -1;

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

	return go;
}

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