Submission #1018702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018702		j_vdd16	Stations (IOI20_stations)	C++17	100 / 100	632 ms	1284 KiB

stations

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

vvi adj;
vi labels;
int counter = 0;
void dfs(int node, int parent, bool isFirst)
{
	if (isFirst)
		labels[node] = counter++;

	for (int child : adj[node])
	{
		if (child == parent)
			continue;

		dfs(child, node, !isFirst);
	}

	if (!isFirst)
		labels[node] = counter++;
}

vi label(int n, int k, vi u, vi v)
{
	counter = 0;
	labels.assign(n, 0);
	adj.assign(n, {});

	loop(i, n - 1)
	{
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	dfs(0, -1, true);

	return labels;
}


int find_next_station(int s, int t, vi c)
{
	sort(all(c));
	if (c.back() < s)
	{
		if (t > s || t <= c[0])
			return c[0];

		for (int i = c.size() - 1; i >= 0; i--)
		{
			if (t >= c[i])
				return c[i];
		}
	}
	else
	{
		if (t < s || t >= c.back())
			return c.back();

		for (int i = 0; i < c.size(); i++)
		{
			if (t <= c[i])
				return c[i];
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, vi)':
stations.cpp:88:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int i = 0; i < c.size(); i++)
      |                   ~~^~~~~~~~~~
stations.cpp:94:1: warning: control reaches end of non-void function [-Wreturn-type]
   94 | }
      | ^

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