Submission #547246

#	Time	Username	Problem	Language	Result	Execution time	Memory
547246		MilosMilutinovic	Keys (IOI21_keys)	C++17	100 / 100	923 ms	81224 KiB

keys

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

using namespace std;

typedef vector<int> vi;

#define N   600001

int que[N], que_[N], head, tail, *ej[N], *ec[N], eo[N];
int ds[N], gg[N], *ej_[N], eo_[N], ff[N], col[N];
int n, id, tt[N], *wi[N], wo[N], vis[N], td;

void append_(int i, int j) {
	int o = eo_[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej_[i] = (int *) realloc(ej_[i], o * 2 * sizeof ej_[i]);
	ej_[i][o] = j;
}

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

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof ej[i]),
		ec[i] = (int *) realloc(ec[i], o * 2 * sizeof ec[i]);
	ej[i][o] = j, ec[i][o] = c;
}

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

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	ds[i] = j;
}

void upd(int i) {
	ff[i] = 1, que_[td++] = i;
	while (wo[i] > 0) {
		int i_ = wi[i][--wo[i]];

		if (!vis[i_])
			vis[i_] = 1, que[tail++] = i_;
	}
}

int st;

void add(int i) {
	int o;

	upd(col[i]);
	vis[i] = 1;
	if (find(i) != find(st))
		return;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], c = ec[i][o];

		if (vis[j])
			continue;
		if (ff[c] == 1)
			que[tail++] = j, vis[j] = 1;
		else
			que_[td++] = c, wi[c][wo[c]++] = j;
	}
}

void bfs(int i) {
	int i_, o;

	st = i, head = tail = td = 0;
	que[tail++] = i;
	while (head < tail) {
		i_ = que[head++];

		if (find(i_) != find(i)) {
			id = i_;
			break;
		}
		add(i_);
	}
	for (i_ = 0; i_ < tail; i_++)
		vis[que[i_]] = 0;
	for (i_ = 0; i_ < td; i_++)
		ff[que_[i_]] = 0, wo[que_[i_]] = 0;
}

vi find_reachable(vi aa, vi ii_, vi jj_, vi cc) {
	static int ii[N], jj[N], hh[N];
	int m = ii_.size(), i, j, i_, mn, op, cnt;
	vi ans(n = aa.size());

	for (i = 0; i < n; i++)
		ej_[i] = (int *) malloc(2 * sizeof *ej_[i]),
		ej[i] = (int *) malloc(2 * sizeof *ej[i]),
		ec[i] = (int *) malloc(2 * sizeof *ec[i]);
	for (i = 0; i < m; i++)
		append(ii_[i], jj_[i], cc[i]), append(jj_[i], ii_[i], cc[i]);
	for (i = 0; i < n; i++)
		ds[i] = i, gg[i] = 0;
	for (i = 0; i < n; i++)
		col[i] = aa[i], tt[aa[i]]++;
	for (i = 0; i < m; i++)
		tt[cc[i]]++;
	for (i = 0; i < N; i++)
		if (tt[i] >= 1)
			wi[i] = (int *) malloc(2 * tt[i] * sizeof *wi[i]), wo[i] = 0;
	cnt = 0;
	for (i_ = 0; i_ < 20; i_++) {
		op = 0;

		for (i = 0; i < n; i++)
			if (find(i) == i && gg[i] == 0) {
				id = -1;
				bfs(i);
				if (id == -1) {
					gg[i] = 1, hh[cnt++] = i;
					for (j = 0; j < tail; j++)
						append_(i, que[j]);
				} else
					ii[op] = i, jj[op++] = id;
			}
		for (i = 0; i < op; i++)
			join(ii[i], jj[i]);
	}
	for (i = 0, mn = n + 1; i < cnt; i++)
		mn = min(mn, eo_[hh[i]]);
	for (i = 0; i < cnt; i++)
		if (eo_[hh[i]] == mn)
			for (j = 0; j < eo_[hh[i]]; j++)
				ans[ej_[hh[i]][j]] = 1;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void append_(int, int)':
keys.cpp:19:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   19 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
keys.cpp: In function 'void append(int, int, int)':
keys.cpp:27:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
keys.cpp: In function 'void bfs(int)':
keys.cpp:77:10: warning: unused variable 'o' [-Wunused-variable]
   77 |  int i_, o;
      |          ^

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