Submission #985469

#	Time	Username	Problem	Language	Result	Execution time	Memory
985469		HerreraDaniel	Stations (IOI20_stations)	C++17	0 / 100	603 ms	1108 KiB

stations

#include "stations.h"

#include <bits/stdc++.h>
#define pb(x) push_back((x))
using namespace std;

int countBits(int k) {
	int ans = 0;

	while (k) ans++, k >>= 1;
	return ans;
}

void setLabel(const int v, const int p, int i, const int& mask,
              const int& maskSz, vector<int>& labels,
              const vector<vector<int>>& g) {
	labels[v] = (i << maskSz) | mask;
	for (const int& nei : g[v])
		if (nei != p)
			setLabel(nei, v, i + 1, mask, maskSz, labels, g);
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);

	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; i++)
		g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);

	int root = -1, leaf = -1;
	for (int i = 0; root == -1 && i < n; i++)
		if (g[i].size() > 2) root = i;
		else if (g[i].size() == 1)
			leaf = i;

	if (root == -1) root = leaf;

	labels[root] = 0;
	int reserved = countBits(g[root].size() - 1);

	for (unsigned long long m = 0; m < g[root].size(); m++) {
		setLabel(g[root][m], root, 1, m, reserved, labels, g);
	}

	return labels;
}

int findSize(int a, int b) {
	for (int i = 0; i < 11; i++) {
		int na = (a >> i), nb = (b >> i);
		if (abs(nb - na) != 1) continue;
		return i;
	}

	return -1;
}

int find_next_station(int s, int t, vector<int> c) {
	if (c.size() == 1) return c[0];  // Leaf only have 1 way to go

	int maskSz  = findSize(s, c[c.size() - 1]);
	int bitmask = ((1 << (maskSz + 1)) - 1);

	if (!s) return (bitmask & t);

	if ((bitmask & s) != (bitmask & t)) return c[0];
	s >>= maskSz, t >>= maskSz;
	if (t > s) return c[1];
	return c[0];
}

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