Submission #1351771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351771		MuhammadSaram	Stations (IOI20_stations)	C++20	100 / 100	293 ms	592 KiB

stations

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

using namespace std;

const int M = 1000 + 1;

vector<int> nei[M];
int dep[M], st[M], en[M],  t;

void dfs(int u,int p=-1)
{
	st[u]=t++;
	for (int i:nei[u])
		if (i!=p)
			dep[i]=dep[u]+1, dfs(i,u);
	en[u]=t++;
}

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	t=0;
	for (int i=0;i<n;i++) nei[i].clear();
	for (int i=0;i<n-1;i++)
		nei[u[i]].push_back(v[i]), nei[v[i]].push_back(u[i]);
	dfs(0);
	vector<pair<int,int>> v1;
	for (int i=0;i<n;i++)
	{
		if (dep[i]%2==0) v1.push_back({st[i],i});
		else v1.push_back({en[i],i});
	}
	sort(v1.begin(), v1.end());
	vector<int> ans(n);
	for (int i=0;i<n;i++)
		ans[v1[i].second]=i;
	return ans;
}

int find_next_station(int s, int t, vector<int> c)
{
	int m=c.size();
	sort(c.begin(), c.end());
	if (s<c[0])
	{
		int x=1;
		if (!s) x=0;
		if (s<t && m>x && t<=c[m-1-x])
		{
			for (int i=0;i<m;i++)
				if (c[i]>=t)
					return c[i];
		}
		else
			return c[m-1];
	}
	else
	{
		if (m>1 && s>t && c[1]<=t)
		{
			for (int i=m-1;i>=0;i--)
				if (c[i]<=t)
					return c[i];
		}
		else
			return c[0];
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

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