Submission #467611

#	Time	Username	Problem	Language	Result	Execution time	Memory
467611		rainboy	Keys (IOI21_keys)	C++17	100 / 100	1330 ms	215220 KiB

keys

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

using namespace std;

typedef vector<int> vi;

const int N = 300000, M = 300000, L = 19, N_ = 1 + (N + M * 2) * (L + 1), INF = 0x3f3f3f3f;	/* L = ceil(log2(N)) */

int ii[M], jj[M], nxt[M * 2];
int ll[N_], rr[N_], head[N_], tail[N_], _; char available[N_], has[N_];
int n;

void pul_leaf(int t) {
	has[t] = available[t] && head[t] != -1;
}

void pul(int t) {
	has[t] = has[ll[t]] || has[rr[t]];
}

void push(int t, int h) {
	if (head[t] == -1)
		head[t] = tail[t] = h;
	else
		nxt[tail[t]] = h, tail[t] = h;
}

int pop(int t) {
	int h = head[t];

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

int update(int t, int l, int r, int c, int h) {
	if (t == 0)
		t = ++_, head[t] = tail[t] = -1;
	if (r - l == 1) {
		if (h != -1)
			push(t, h);
		else
			available[t] = 1;
		pul_leaf(t);
	} else {
		int m = (l + r) / 2;

		if (c < m)
			ll[t] = update(ll[t], l, m, c, h);
		else
			rr[t] = update(rr[t], m, r, c, h);
		pul(t);
	}
	return t;
}

int merge(int t1, int t2, int l, int r) {
	int m;

	if (t1 == 0)
		return t2;
	if (t2 == 0)
		return t1;
	if (r - l == 1) {
		available[t1] |= available[t2];
		if (head[t1] == -1)
			head[t1] = head[t2], tail[t1] = tail[t2];
		else if (head[t2] != -1)
			nxt[tail[t1]] = head[t2], tail[t1] = tail[t2];
		pul_leaf(t1);
	} else {
		m = (l + r) / 2;
		ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
		pul(t1);
	}
	return t1;
}

int find_(int i);

int query(int t, int l, int r, int i) {
	if (!has[t])
		return -1;
	if (r - l == 1) {
		while (head[t] != -1) {
			int h = pop(t), j = i ^ find_(ii[h]) ^ find_(jj[h]);

			if (j != i) {
				pul_leaf(t);
				return j;
			}
		}
		pul_leaf(t);
		return -1;
	} else {
		int m = (l + r) / 2, j;

		if ((j = query(ll[t], l, m, i)) != -1) {
			pul(t);
			return j;
		}
		if ((j = query(rr[t], m, r, i)) != -1) {
			pul(t);
			return j;
		}
		pul(t);
		return -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], tt[N];

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

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, tt[i] = merge(tt[i], tt[j], 0, n);
}

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

void get(int i) {
	int j = query(tt[i], 0, n, i);

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

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

	for (h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h];
	for (i = 0; i < n; i++)
		tt[i] = update(tt[i], 0, n, aa[i], -1);
	for (h = 0; h < m * 2; h++)
		nxt[h] = -1;
	for (h = 0; h < m; h++) {
		i = ii[h], j = jj[h];
		tt[i] = update(tt[i], 0, n, cc[h], h << 1 | 0), tt[j] = update(tt[j], 0, n, 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: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33