Submission #395931

#	Time	Username	Problem	Language	Result	Execution time	Memory
395931		jeroenodb	Stations (IOI20_stations)	C++14	100 / 100	1128 ms	784 KiB

stations

#include "stations.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
int cnt = 0;
void dfs(vvi& adj, vi& label, int at=0, int from=-1, bool odd = false) {
	if(!odd) label[at] = cnt++;
	for(int to: adj[at]) if(to!=from) {
		dfs(adj,label,to,at,!odd);
	}
	if(odd) label[at] = cnt++;
}
vi label(int n, int k, vector<int> u, vector<int> v) {
	vi labels(n);
	cnt=0;
	vvi adj(n);
	for(int i=0;i<n-1;++i) {
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	dfs(adj,labels);
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	for(int to: c) if(to==t) return to;
	if(s<c[0]) {
		// s has in label
		int parentout = c.back();
		c.insert(c.begin(),s);
		int n = c.size();
		for(int i=1;i<n;++i) {
			if(c[i-1]< t and t<c[i]) {
				return c[i];
			}
		}
		return parentout;
	} else {
		// s has out label
		
		int parentin = c[0];
		c.push_back(s);
		int n = c.size();
		for(int i=2;i<n;++i) {
			if(c[i-1]<t and t <c[i]) {
				return c[i-1];
			}
		}
		return parentin;


	}
}
  

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