Submission #623232

#	Time	Username	Problem	Language	Result	Execution time	Memory
623232		AriaH	Stations (IOI20_stations)	C++17	0 / 100	3162 ms	2097152 KiB

stations

#include "stations.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define endl "\n"
#define F first
#define S second
#define Mp make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie()

const int N = 1e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;

int ptr = -1, H[N], St[N], Fi[N];

vector < int > G[N];

void dfs(int v, int P = -1)
{
	St[v] = ++ ptr;
	for(auto u : G[v])
	{
		if(u == P) continue;
		H[u] = H[v] + 1;
		dfs(u, v);
	}
	Fi[v] = ++ ptr;
}

vector < int > label(int n, int k, vector < int > A, vector < int > B)
{
	vector < int > ret(n);
	for(int i = 0; i < n - 1; i ++)
	{
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	dfs(0, -1);
	for(int i = 0; i < n; i ++)
	{
		if(H[i] & 1)
		{
			ret[i] = Fi[i];
		}
		else
		{
			ret[i] = St[i];
		}
	}
	/*for(int i = 0; i < n; i ++)
	{
		printf("%d ", ret[i]);
	}
	printf("\n");*/
	return ret;
}

int find_next_station(int s, int t, vector < int > c)
{
	int sz = SZ(c);
	sort(all(c));
	int tp = 1;
	for(auto u : c)
	{
		if(u > s) tp = 0;
	}
	if(s == 0)
	{
		int id = lower_bound(all(c), t) - c.begin();
		return c[id];
	}
	if(tp == 0)
	{
		if(t < s) return c.back();
		int id = lower_bound(all(c), t) - c.begin();
		if(id <= sz - 2)
		{
			return c[id];
		}
		return c.back();
	}
	if(t > s) return c[0];
	if(t <= c[0]) return c[0];
	int id = upper_bound(all(c), t) - c.begin() - 1;
	return c[id];
}

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