Submission #308161

#	Time	Username	Problem	Language	Result	Execution time	Memory
308161		jwvg0425	Stations (IOI20_stations)	C++17	100 / 100	991 ms	1152 KiB

stations

#include "stations.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

struct Solver
{
	vector<int> edge[1005];
	int in[1005] = { 0, }, out[1005] = { 0, };
	int depth[1005] = { 0, };
	int vis = 0;

	void dfs(int root)
	{
		if (depth[root] % 2 == 0)
		{
			in[root] = vis;
			vis++;
		}

		for (auto& e : edge[root])
		{
			edge[e].erase(find(all(edge[e]), root));
			depth[e] = depth[root] + 1;
			dfs(e);
		}

		if (depth[root] % 2 == 1)
		{
			out[root] = vis;
			vis++;
		}
	}
};

vector<int> label(int n, int k, vector<int> u, vector<int> v)
{
	Solver s;
	for (int i = 0; i < n - 1; i++)
	{
		s.edge[u[i]].push_back(v[i]);
		s.edge[v[i]].push_back(u[i]);
	}

	s.dfs(0);

	vector<int> res(n);
	for (int i = 0; i < n; i++)
	{
		if (s.depth[i] % 2 == 0)
			res[i] = s.in[i];
		else
			res[i] = s.out[i];
	}

	return res;
}

int find_next_station(int s, int t, vector<int> c)
{
	// s = in time, cs = out time
	if (s < c[0])
	{
		int pc = s;
		for (int i = 0; i < c.size(); i++)
		{
			if (t > pc && t <= c[i])
				return c[i];

			pc = c[i];
		}

		return c.back();
	}
	else
	{
		// s = out time, cs = in time
		for (int i = 0; i < c.size(); i++)
		{
			int nc = (i == c.size() - 1) ? (s + 1) : c[i + 1];
			if (t >= c[i] && t < nc)
				return c[i];
		}

		return c[0];
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for (int i = 0; i < c.size(); i++)
      |                   ~~^~~~~~~~~~
stations.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int i = 0; i < c.size(); i++)
      |                   ~~^~~~~~~~~~
stations.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |    int nc = (i == c.size() - 1) ? (s + 1) : c[i + 1];
      |              ~~^~~~~~~~~~~~~~~

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