Submission #1042659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042659		parsadox2	Stations (IOI20_stations)	C++17	5 / 100	532 ms	964 KiB

stations

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

using namespace std;

const int N = 1e3 + 10;
int n , tim , st_tim[N] , fn_tim[N] , dis[N];
vector <int> adj[N];

void Dfs(int v , int p = -1)
{
	st_tim[v] = tim;
	tim++;
	for(auto u : adj[v])  if(u != p)
	{
		dis[u] = (dis[v] ^ 1);
		Dfs(u , v);
	}
	fn_tim[v] = tim;
	tim++;
}

vector<int> label(int nn, int k, vector<int> u, vector<int> v) {
	n = nn;
	for(int i = 0 ; i < n ; i++)
	{
		dis[i] = 0;
		adj[i].clear();
	}
	tim = 0;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}
	int root = -1;
	for(int i = 0 ; i < n ; i++)  if(adj[i].size() == 1)
		root = i;
	Dfs(root);
	vector <int> all;
	for(int i = 0 ; i < n ; i++)
	{
		if(dis[i] == 0)
			all.push_back(st_tim[i]);
		else
			all.push_back(fn_tim[i]);
	}
	sort(all.begin() , all.end());
	vector<int> labels(n);
	for (int i = 0; i < n; i++) 
	{
		if(dis[i] == 0)
			labels[i] = lower_bound(all.begin() , all.end() , st_tim[i]) - all.begin();
		else
			labels[i] = lower_bound(all.begin() , all.end() , fn_tim[i]) - all.begin();
	}
	return labels;
}

int find_next_station(int s, int t, vector<int> c) {
	if(c.size() == 1)
		return c[0];
	if(c[0] > s)
	{
		int par = c.back();
		c.pop_back();
		int mn = s , mx = c.back();
		if(t < mn || t > mx)
			return par;
		int ans = N;
		for(auto u : c)  if(t <= u)
		{
			ans = u;
			break;
		}
		return ans;
	}
	else
	{
		int par = c[0];
		int mn = c[1] , mx = s;
		if(t < mn || t > mx)
			return par;
		int ans = N;
		for(int i = c.size() - 1 ; i > 0 ; i--)  if(c[i] <= ans)
		{
			ans = c[i];
			break;
		}
		return ans;
	}
}

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