Submission #1149534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149534		PagodePaiva	Stations (IOI20_stations)	C++20	100 / 100	302 ms	648 KiB

stations

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

using namespace std;

const int N = 1010;
vector <int> g[N];
int tin[N], sz[N], h[N], tout[N];
int tmm;

void dfs(int v, int p){
	tin[v] = tmm;
	tmm++;
	sz[v] = 1;
	for(auto x : g[v]){
		if(x == p) continue;
		h[x] = h[v]+1;
		dfs(x, v);
		sz[v] += sz[x];
	}
	tout[v] = tmm;
	tmm++;
	return;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for(int i = 0;i < n;i++){
		g[i].clear();
		tin[i] = sz[i] = tout[i] = h[i] = 0;
	}
	tmm = 0;
	std::vector<int> labels;
	for(int i = 0;i < n-1;i++){
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(0, 0);
	vector <int> aux;
	for(int i = 0;i < n;i++){
		aux.push_back((h[i]%2 == 0 ? tin[i] : tout[i]));
		labels.push_back((h[i]%2 == 0 ? tin[i] : tout[i]));
	}
	sort(aux.begin(), aux.end());
	map <int, int> mp;
	for(int i = 0;i < aux.size();i++)
		mp[aux[i]] = i;
	for(auto &x : labels){
		x = mp[x];
	}
	return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int mn = 2010;
	for(auto x : c){
		mn = min(mn, x);
	}
	if(mn > s){
		if(s == 1){
			sort(c.begin(), c.end());
			vector <int> c_tin = c;
			int ant = s;
			for(int i = 0;i < c.size();i++){
				c_tin[i] = ant+1;
				ant = c[i];
			}
			for(int i = 0;i+1 < c.size();i++){
				if(c_tin[i] <= t and t <= c[i]) return c[i];
			}
			return c.back();
		}
		else{
			sort(c.begin(), c.end());
			vector <int> c_tin = c;
			int ant = s;
			for(int i = 0;i+1 < c.size();i++){
				c_tin[i] = ant+1;
				ant = c[i];
			}
			for(int i = 0;i+1 < c.size();i++){
				if(c_tin[i] <= t and t <= c[i]) return c[i];
			}
			return c.back();
		}
	}
	else{
		sort(c.begin(), c.end());
		reverse(c.begin(), c.end());
		int ant = s;
		vector <int> c_tout = c;
		for(int i = 0;i+1 < c.size();i++){
			c_tout[i] = ant-1;
			ant = c[i];
		}
		for(int i = 0;i+1 < c.size();i++){
			if(c[i] <= t and t <= c_tout[i]) return c[i];
		}
		return c.back();
	}
}

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