oj.uz

Submission #985453

# Submission time Handle Problem Language Result Execution time Memory
985453 2024-05-17T21:25:46 Z HerreraDaniel Stations (IOI20_stations) C++17
0 / 100
 1 ms 600 KB 
#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;
	for (int i = 0; root == -1 && i < n; i++)
		if (g[i].size() > 2) root = i;

	labels[root] = 0;
	int 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);

	abort();
	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.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 61.0

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