Submission #1232992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232992		repsak	Stations (IOI20_stations)	C++20	30.95 / 100	311 ms	600 KiB

stations

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

void dfs(int u, int parent, int& num, vector<int>& enter, vector<int>& exit, vector<vector<int>>& adj){
	enter[u] = num;
	num++;

	for(auto v : adj[u]){
		if(v == parent) continue;
		dfs(v, u, num, enter, exit, adj);
	}

	exit[u] = num;
	num++;
}	

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	int N = n;
	vector<vector<int>> adj(N);
	vector<int> enter(N), exit(N);

	for(int i = 0; i < N - 1; i++){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	vector<int> labels(n);

	int num = 0;
	dfs(0, -1, num, enter, exit, adj);

	for(int i = 0; i < N; i++){
		labels[i] = (enter[i] << 11) + exit[i];
		// labels[i] = (enter[i] + 1) * 10000 + (exit[i] + 1);
	}

	return labels;
}

pair<int, int> convert(int s){
	int sIn = s >> 11;
	int sOut = s % (1 << 11);
    // int sIn  = (s / 10000) - 1;
	// int sOut = (s % 10000) - 1;

	return {sIn, sOut};
}

int find_next_station(int s, int t, vector<int> c) {
	if(c.size() == 1) return c[0];

	auto [sIn, sOut] = convert(s); 
	auto [tIn, tOut] = convert(t); 

	for(auto child : c){
		auto [cIn, cOut] = convert(child);


		if(cIn <= tIn && cOut >= tOut && cIn >= sIn && cOut <= sOut){
			// cout  << "->" << child << "<-\n";
			return child;
		}
	}
	
	for(auto child : c){
		auto [cIn, cOut] = convert(child);
		if(cIn <= sIn && cOut >= sOut){
			// cout  << "->" << child << "<-\n";
			return child;
		}
	}

	// cout << "INVALID\n";
	return c[0];
}

// #include "stub.cpp"

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