Submission #1018090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018090		Boas	Stations (IOI20_stations)	C++17	52.32 / 100	627 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 nrMx;
int curNr = 0;

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

vi label(int n, int k, vi u, vi v)
{
	curNr = 0;
	nrs = vi(n);
	nrMx = vi(n);
	adj = vvi(n);
	loop(u.size(), i)
	{
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	int start = 0;
	loop(n, i)
	{
		if (adj[i].size() == 1)
		{
			start = i;
			break;
		}
	}
	DFS(start);
	vi labels(n);
	for (int i = 0; i < n; i++)
	{
		labels[i] = 1000 * nrs[i] + nrMx[i];
	}
	return labels;
}

int find_next_station(int s, int t, vi c)
{
	int nrMax = s % 1000;
	int nr = s / 1000;
	int nrGoal = t / 1000;
	if (nrGoal > nrMax || nrGoal < nr)
	{
		// smallest number, so to the root
		return c[0];
	}
	for (int l : c)
	{
		int nrC = l / 1000;
		if (nrC < nr)
			continue;
		int nrCMax = l % 1000;
		if (nrGoal <= nrCMax && nrGoal >= nrC)
			return l;
	}
	// throw;
	return 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++)
......
   37 |  loop(u.size(), i)
      |                                       
stations.cpp:37:2: note: in expansion of macro 'loop'
   37 |  loop(u.size(), i)
      |  ^~~~

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