Submission #1046636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046636		mariaclara	Stations (IOI20_stations)	C++17	100 / 100	543 ms	1452 KiB

stations

#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> trio;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first 
#define sc second

int t;
vector<tuple<int,int,int>> val;
vector<int> labels;
vector<vector<int>> edges;

void dfs(int x, int pai, int niv) {
	t++;
	if(niv%2 == 0) labels[x] = t;

	for(int viz : edges[x]) if(viz != pai) dfs(viz, x, niv+1);

	if(niv%2 == 1) labels[x] = t;
	val.pb({labels[x], niv, x});
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	labels.clear();
	edges.clear();
	val.clear();
	labels.resize(n);
	edges.resize(n);
	t = -1;
	
	for(int i = 0; i < n-1; i++) edges[u[i]].pb(v[i]), edges[v[i]].pb(u[i]);

	dfs(0, -1, 0);
	sort(all(val), [](trio a, trio b){
		if(get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
		return get<1>(a) > get<1>(b);
	});

	for(int i = 0; i < n; i++) {
		int ind = get<2>(val[i]);
		labels[ind] = i;
	}

	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	// primeiro descobrir se S guarda t_in ou t_out
	// se S guarda t_out, então t_in[viz] < t_out[s]
	// caso contrario, t_out[viz] > t_in[s]

	if(sz(c) == 1) return c[0];

	if(c.back() < s) {
		// S guarda t_out
		int t_in = c[1] - 1, t_out = s;
		if(t < t_in or t_out < t) return c[0];
		// caso contrário t está na sub de s
		// sub[viz] = {t_in[viz], t_in[viz+1]-1}
		// basta achar o primeiro cara tal que x < c[viz], a resposta é o cara anterior
		auto ptr = upper_bound(all(c), t);
		ptr--;
		return *ptr;
	}
	else {
		// S guarda t_in
		int t_in = s, t_out = c[sz(c) - 2];
		if(t < t_in or t_out < t) return c.back();
		// caso contrário t está na sub de s
		// sub[viz] = {t_out[viz-1]+1, t_out[viz]}
		auto ptr = lower_bound(all(c), t);
		return *ptr;
	}
}

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