Submission #467597

#	Time	Username	Problem	Language	Result	Execution time	Memory
467597		rainboy	열쇠 (IOI21_keys)	C++17	39 / 100	319 ms	103788 KiB

keys

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

using namespace std;

typedef vector<int> vi;

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

int ii[M], jj[M], nxt[M * 2], head[N][C], tail[N][C]; char available[N][C];

void append(int i, int c, int h) {
	if (head[i][c] == -1)
		head[i][c] = tail[i][c] = h;
	else
		nxt[tail[i][c]] = h, tail[i][c] = h;
}

int pop(int i, int c) {
	int h = head[i][c];

	if ((head[i][c] = nxt[h]) == -1)
		tail[i][c] = -1;
	return h >> 1;
}

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;

	for (c = 0; c < C; c++) {
		available[i][c] |= available[j][c];
		if (head[i][c] == -1)
			head[i][c] = head[j][c], tail[i][c] = tail[j][c];
		else if (head[j][c] != -1)
			nxt[tail[i][c]] = head[j][c], tail[i][c] = tail[j][c];
	}
}

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

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);
}

void get(int i) {
	int c;

	pp[i] = -1;
	for (c = 0; c < C; c++)
		if (available[i][c])
			while (head[i][c] != -1) {
				int h = pop(i, c), j = i ^ find_(ii[h]) ^ find_(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 cc) {
	int n = aa.size(), m = ii_.size(), h, i, j, c, mn;
	vi ans(n);

	for (h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h];
	for (i = 0; i < n; i++)
		available[i][aa[i]] = 1;
	for (i = 0; i < n; i++)
		for (c = 0; c < C; c++)
			head[i][c] = tail[i][c] = -1;
	for (h = 0; h < m * 2; h++)
		nxt[h] = -1;
	for (h = 0; h < m; h++)
		append(ii[h], cc[h], h << 1 | 0), append(jj[h], cc[h], h << 1 | 1);
	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 = find_(pp[i]); j != find_(i); j = find_(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: 9 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 30 / 30
• Subtask 5: 0 / 33