Submission #1085301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085301		4QT0R	Stations (IOI20_stations)	C++17	100 / 100	632 ms	1276 KiB

stations

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

vector<int> label(int n, int k, vector<int> u, vector<int> v){
	vector<vector<int>> graph(n);
	vector<int> dep(n);
	int timer=0;
	vector<int> pre(n);
	vector<int> post(n);
	for (int i = 0; i<n-1; i++){
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	auto dfs = [&](int v, int p, auto &&dfs) -> void{
		pre[v]=timer++;
		for (auto u : graph[v]){
			if (u==p)continue;
			dep[u]=dep[v]+1;
			dfs(u,v,dfs);
		}
		post[v]=timer++;
	};
	dfs(0,-1,dfs);
	int iter=0;
	set<int> s;
	map<int,int> mp;
	for (int i = 0; i<n; i++)s.insert(dep[i]&1?post[i]:pre[i]);
	for (auto x : s)mp[x]=iter++;
	vector<int> ans(n);
	for (int i = 0; i<n; i++){
		ans[i]=mp[dep[i]&1?post[i]:pre[i]];
	}
	return ans;
}


int find_next_station(int s, int t, vector<int> c){
	int cas=1;
	for (auto u : c)if (s<u)cas=0;
	if (cas){
		int fat=c[0];
		c.erase(c.begin());
		int prv=s;
		for (int i = c.size()-1; i>=0; i--){
			if (c[i]<=t && t<prv)return c[i];
			prv=c[i];
		}
		return fat;
	}
	else{
		int fat=c.back();
		c.pop_back();
		int prv=s;
		for (int i = 0; i<c.size(); i++){
			if (prv<t && t<=c[i])return c[i];
			prv=c[i];
		}
		return fat;

	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i<c.size(); i++){
      |                   ~^~~~~~~~~

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