Submission #467577

#	Time	Username	Problem	Language	Result	Execution time	Memory
467577		rainboy	Keys (IOI21_keys)	C++17	0 / 100	1 ms	544 KiB

keys

#include <vector>
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 300000, M = 300000, C = 30, INF = 0x3f3f3f3f;

int ii[M], jj[M], bb[M];
int *eh[N][C], eo[N][C], eo_[N][C]; char available[N][C];

void append(int i, int h) {
	int c = bb[h], o = eo[i][c]++;

	if (o == eo_[i][c])
		eh[i][c] = (int *) realloc(eh[i][c], (eo_[i][c] *= 2) * sizeof *eh[i]);
	eh[i][c][o] = h;
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int ds_[N];

int find_(int i) {
	return ds_[i] < 0 ? i : (ds_[i] = find_(ds_[i]));
}

void merge(int i, int j) {
	int c, o;

	for (c = 0; c < C; c++) {
		available[i][c] |= available[j][c];
		for (o = eo[j][c]; o--; )
			append(i, eh[j][c][o]);
		free(eh[j][c]);
	}
}

void join_(int i, int j) {
	int tmp;

	i = find_(i);
	j = find_(j);
	if (i == j)
		return;
	if (ds_[i] > ds_[j])
		tmp = i, i = j, j = tmp;
	ds_[i] += ds_[j], ds_[j] = i, merge(i, j);
}

int pp[N], qu[N], cnt;

void get(int i) {
	int c;

	pp[i] = -1;
	for (c = 0; c < C; c++)
		if (available[i][c])
			while (eo[i][c]) {
				int h = eh[i][c][--eo[i][c]], j = find_(i ^ ii[h] ^ jj[h]);

				if (j != i) {
					pp[i] = j;
					if (!join(i, j))
						qu[cnt++] = i;
					return;
				}
			}
}

vi find_reachable(vi aa, vi ii_, vi jj_, vi bb_) {
	int n = aa.size(), m = ii_.size(), h, i, j, c, mn;
	vi ans(n);

	for (i = 0; i < n; i++)
		for (c = 0; c < C; c++)
			eh[i][c] = (int *) malloc((eo_[i][c] = 2) * sizeof *eh[i][c]);
	for (h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h], bb[h] = bb_[h];
	for (i = 0; i < n; i++)
		available[i][aa[i]] = 1;
	for (h = 0; h < m; h++)
		append(ii[h], h), append(jj[h], h);
	memset(ds, -1, n * sizeof *ds), memset(ds_, -1, n * sizeof *ds_);
	for (i = 0; i < n; i++)
		get(i);
	while (cnt--) {
		i = qu[cnt];
		for (j = pp[i]; j != i; j = pp[j])
			join_(i, j);
		get(find_(i));
	}
	mn = INF;
	for (i = 0; i < n; i++)
		if (ds_[i] < 0 && pp[i] == -1)
			mn = min(mn, -ds_[i]);
	for (i = 0; i < n; i++)
		ans[i] = pp[find_(i)] == -1 && -ds_[find_(i)] == mn;
	return ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33