Submission #1180273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180273		Pacybwoah	Stations (IOI20_stations)	C++20	100 / 100	301 ms	560 KiB

stations

#include "stations.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
namespace{
	vector<vector<int>> graph;
	vector<int> in, dep, out;
	int cnt = 0;
	const int inf = 1e9;
	void dfs(int node, int parent){
		in[node] = cnt;
		dep[node] = dep[parent] + 1;
		cnt++;
		for(auto &x: graph[node]){
			if(x != parent) dfs(x, node);
		}
		out[node] = cnt;
		cnt++;
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v){
	vector<int>().swap(in);
	vector<int>().swap(dep);
	vector<int>().swap(out);
	vector<vector<int>>().swap(graph);
	in.resize(n);
	graph.resize(n);
	out.resize(n);
	dep.resize(n);
	cnt = 0;
	for(int i = 0; i < n - 1; i++){
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	dfs(0, 0);
	vector<int> ret(n), cp;
	for(int i = 0; i < n; i++){
		if(dep[i] & 1) cp.push_back(in[i]), ret[i] = in[i];
		else cp.push_back(out[i]), ret[i] = out[i];
	}
	sort(cp.begin(), cp.end());
	for(int i = 0; i < n; i++){
		ret[i] = lower_bound(cp.begin(), cp.end(), ret[i]) - cp.begin();
	}
	return ret;
}

int find_next_station(int s, int t, std::vector<int> c){
	int sz = (int)c.size();
	if(s < c[0]){
		int l = s + 1;
		for(int i = 0; i < sz - 1; i++){
			int r = c[i];
			if(l <= t && t <= r) return c[i];
			l = c[i] + 1;
		}
		return c[sz - 1];
	}
	else{
		reverse(c.begin(), c.end());
		int r = s - 1;
		for(int i = 0; i < sz - 1; i++){
			int l = c[i];
			if(l <= t && t <= r) return c[i];
			r = c[i] - 1;
		}
		return c[sz - 1];
	}
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g stations.cpp stub.cpp

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