제출 #985451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
985451		HerreraDaniel	Stations (IOI20_stations)	C++17	0 / 100	3060 ms	772 KiB

stations

#include "stations.h"

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

using ll = long long;

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

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

void setLabel(const ll v, const ll p, ll i, const ll& mask,
              const ll& maskSz, vector<int>& labels,
              const vector<vector<ll>>& g) {
	labels[v] = (i << maskSz) | mask;
	for (const ll& 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<ll>> g(n);
	for (int i = 0; i < n - 1; i++)
		g[u[i]].pb(v[i]), g[v[i]].pb(u[i]);

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

	labels[root] = 0;
	ll reserved  = countBits(g[root].size());

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

	return labels;
}

ll findSize(ll a, ll b) {
	for (int i = 0; i < 11; i++) {
		ll 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

	ll maskSz  = findSize(s, c[c.size() - 1]);
	ll 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