제출 #824753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
824753		fatemetmhr	Stations (IOI20_stations)	C++17	100 / 100	668 ms	5544 KiB

stations

// Be name khoda //



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

using namespace std;

#define debug(x) cerr << "(" << #x << "):" << x << endl;
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back
#define mp       make_pair

const int maxn5 = 1e5 + 10;

vector <int> ret, adj[maxn5];
int h[maxn5], st[maxn5], ft[maxn5], ti;
bool mark[maxn5];

void dfs(int v){
	mark[v] = true;
	st[v] = ++ti;
	for(auto u : adj[v]) if(!mark[u]){
		h[u] = h[v] + 1;
		dfs(u);
	}
	ft[v] = ++ti;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	ret.clear();
	ret.resize(n);
	h[0] = 0;
	ti = -1;
	fill(mark, mark + n + 4, false);
	for(int i = 0; i < n; i++){
		adj[i].clear();
	}
	for(int i = 0; i < n - 1; i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	dfs(0);
	for(int i = 0; i < n; i++){
		if(h[i] & 1)
			ret[i] = ft[i];
		else
			ret[i] = st[i];
	}
	vector <int> num; num.clear();
	for(int i = 0; i < n; i++)
		num.pb(ret[i]);
	sort(all(num));
	num.resize(unique(all(num)) - num.begin());
	for(int i = 0; i < n; i++){
		ret[i] = lower_bound(all(num), ret[i]) - num.begin();
	}
	return ret;
}

int find_next_station(int s, int t, std::vector<int> c) {
	for(auto u : c) if(u == t)
		return t;
	sort(all(c));
	if(s == 0){
		int pt = upper_bound(all(c), t) - c.begin();
		return c[pt];
	}
	if(c.size() == 1)
		return c[0];
	if(s < c[0]){ // s is st
		int st = s, ft = c[int(c.size()) - 2];
		if(st > t || ft < t){
			return c.back(); // par
		}
		else{
			int pt = upper_bound(all(c), t) - c.begin();
			return c[pt];
		}
	}
	else{ // s is ft
		int ft = s, st = c[1];
		if(st >= t || ft < t)
			return c[0];
		int pt = upper_bound(all(c), t) - c.begin() - 1;
		return c[pt];
	}
}

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