Submission #1228951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228951		unnick	Stations (IOI20_stations)	C++20	0 / 100	308 ms	588 KiB

stations

#include "stations.h"
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> ngb;
vector<int> ss;
vector<int> lb;
int css(int i, int p) {
	int r = 1;
	for (int n: ngb[i]) {
		if (n == p) continue;
		r += css(n, i);
	}
	ss[i] = r;
	return r;
}
void clb(int i, int p, int l, bool d) {
	lb[i] = l;
	for (int n: ngb[i]) {
		if (n == p) continue;
		l += ss[n] * (d ? 1 : -1);
		clb(n, i, l, !d);
	}
}
std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	ngb.resize(0);
	ngb.resize(n);
	ss.resize(n);
	lb.resize(n);
	for (int i = 0; i < u.size(); i++) {
		ngb[u[i]].push_back(v[i]);
		ngb[v[i]].push_back(u[i]);
	}
	css(0, -1);
	clb(0, -1, 0, true);
	// for (int i: lb) cout << i << " ";
	// cout << "\n";
	return lb;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (s == 0) {
		for (int i = 0; i < c.size(); i++) {
			if (t <= c[i]) return c[i];
		}
	}
	bool d = c[0] > s;
	int p = d ? c.back() : c.front();
	if (d) {
		if (t < s) return p;
		if (t >= p) return p;
		for (int i = 0; i < c.size()-1; i++) {
			if (t <= c[i]) return c[i];
		}
	} else {
		if (t > s) return p;
		if (t <= p) return p;
		for (int i = c.size(); i > 0; i++) {
			if (t >= c[i]) return c[i];
		}
	}
}

Compilation message (stderr)

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
   64 | }
      | ^

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