Submission #615890

#	Time	Username	Problem	Language	Result	Execution time	Memory
615890		fvogel499	Stations (IOI20_stations)	C++17	0 / 100	1737 ms	2097152 KiB

stations

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

using namespace std;

vector<int> graph [1000*1000];
vector<int> assign;

int curT;
void dfs(int x, int p = -1, int h = 0) {
	if (h%2 == 0) {
		assign[x] = curT;
		curT++;
	}
	for (int y : graph[x]) if (y != p) {
		dfs(y, x, h+1);
	}
	if (h%2 == 1) {
		assign[x] = curT;
		curT++;
	}
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	for (int i = 0; i < n-1; i++) {
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}
	assign = vector<int>(n, -1);
	curT = 0;
	dfs(0);
	return assign;
}

int find_next_station(int curL, int tarL, std::vector<int> adj) {
	sort(adj.begin(), adj.end());
	if (curL == 0) { // the root
		for (int i : adj) {
			if (tarL <= i) {
				return i;
			}
		}
		assert(false);
	}
	vector<pair<int, pair<int, int>>> ints;
	int parent;
	int range [2] = {curL, curL};
	if (adj[0] > curL) {
		parent = adj.back();
		if (adj.size() >= 2) {
			range[1] = adj[adj.size()-2];
		}
		for (int i = 0; i < adj.size()-1; i++) {
			int bef = curL+1;
			if (i) bef = adj[i-1]+1;
			ints.push_back({adj[i], {bef, adj[i]}});
		}
	}
	else {
		parent = adj[0];
		if (adj.size() >= 2) {
			range[0] = adj[1];
		}
		assert(adj.back() < curL);
		for (int i = 1; i < adj.size(); i++) {
			int aft = curL-1;
			if (i+1 < adj.size()) aft = adj[i+1]-1;
			ints.push_back({adj[i], {adj[i], aft}});
		}
	}
	// if (!(range[0] <= tarL && tarL <= range[1])) {
	// 	return parent;
	// }
	for (auto i : ints) {
		if (i.second.second <= tarL && tarL <= i.second.second) {
			return i.first;
		}
	}
	return parent;
	// assert(false);
	// return -1;
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i < adj.size()-1; i++) {
      |                   ~~^~~~~~~~~~~~~~
stations.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int i = 1; i < adj.size(); i++) {
      |                   ~~^~~~~~~~~~~~
stations.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    if (i+1 < adj.size()) aft = adj[i+1]-1;
      |        ~~~~^~~~~~~~~~~~
stations.cpp:48:6: warning: variable 'range' set but not used [-Wunused-but-set-variable]
   48 |  int range [2] = {curL, curL};
      |      ^~~~~

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