Submission #1034103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034103		Boas	Stations (IOI20_stations)	C++17	100 / 100	611 ms	1280 KiB

stations

#include <bits/stdc++.h>
using namespace std;
#include "stations.h"

#define loop(x, i) for (int i = 0; i < x; i++)
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef set<int> si;
typedef vector<vi> vvi;

vvi adj;
vi nrs;
vi d;
vi nrMx;
int curNr = 0;

void DFS(int i, int prev = -1, int de = 0)
{
	nrs[i] = curNr;
	curNr++;
	d[i] = de;
	for (int j : adj[i])
	{
		if (prev == j)
			continue;
		DFS(j, i, de + 1);
	}
	nrMx[i] = curNr;
	curNr++;
}

vi label(int n, int k, vi u, vi v)
{
	assert(k >= n);
	curNr = 0;
	nrs = vi(n);
	nrMx = vi(n);
	d = vi(n);
	adj = vvi(n);
	loop(u.size(), i)
	{
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	DFS(0);
	si s;
	vi labels(n);
	for (int i = 0; i < n; i++)
	{
		if (d[i] % 2 == 0)
			labels[i] = nrs[i];
		else
			labels[i] = nrMx[i];
		s.insert(labels[i]);
	}
	map<int, int> ix;
	auto it = s.begin();
	for (int i = 0; i < s.size(); i++)
	{
		ix[*it] = i;
		it++;
	}
	for (int &i : labels)
		i = ix[i];
	return labels;
}

int find_next_station(int s, int t, vi c)
{
	if (c.size() == 1)
		return c[0];
	if (s > c[0])
	{
		int nrMax = s;
		int nrGoal = t;
		if (nrGoal > nrMax || nrGoal < c[1])
		{
			// smallest number, so to the root
			return c[0];
		}
		c.pb(s);
		for (int i = 1; i < c.size() - 1; i++)
		{
			int l = c[i];
			if (nrGoal < c[i + 1] && nrGoal >= l)
				return l;
		}
	}
	else if (s == 0)
	{
		c.pb(0);
		for (int i = 1; i < c.size(); i++)
		{
			int l = c[i];
			if (t <= l && t > c[i - 1])
				return l;
		}
	}
	else // s < c[0]
	{
		int nr = s;
		int nrGoal = t;
		if (nrGoal > c[c.size() - 2] || nrGoal < nr)
		{
			// to the root
			return c.back();
		}
		c.insert(c.begin(), s);
		for (int i = 1; i < c.size(); i++)
		{
			int l = c[i];
			if (t <= l && t > c[i - 1])
				return l;
		}
	}
	// throw;
	return c[0];
}

Compilation message (stderr)

stations.cpp: In function 'vi label(int, int, vi, vi)':
stations.cpp:5:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define loop(x, i) for (int i = 0; i < x; i++)
......
   42 |  loop(u.size(), i)
      |                                       
stations.cpp:42:2: note: in expansion of macro 'loop'
   42 |  loop(u.size(), i)
      |  ^~~~
stations.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
stations.cpp: In function 'int find_next_station(int, int, vi)':
stations.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 1; i < c.size() - 1; i++)
      |                   ~~^~~~~~~~~~~~~~
stations.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i = 1; i < c.size(); i++)
      |                   ~~^~~~~~~~~~
stations.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (int i = 1; i < c.size(); i++)
      |                   ~~^~~~~~~~~~

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