oj.uz

Submission #985451

# Submission time Handle Problem Language Result Execution time Memory
985451 2024-05-17T21:22:23 Z HerreraDaniel Stations (IOI20_stations) C++17
0 / 100
 3000 ms 772 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 516 KB Invalid labels (duplicates values). scenario=0, label=9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Invalid labels (duplicates values). scenario=0, label=0
2 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -