Submission #800812

#	Time	Username	Problem	Language	Result	Execution time	Memory
800812		Johann	Keys (IOI21_keys)	C++17	67 / 100	3069 ms	154896 KiB

keys

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<bool> vb;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int MAXN = 300007;

int N, M;
vvi dag;
vi R;
vi P;
vi num, low;
stack<int> st;
vb active;
vector<map<int, vi>> npk; // neighbors per key
vvi nodesInC;			  // nodes in component
vector<set<int>> keys;	  // keys per node
vvi todo;				  // nodes to to from a given node

struct unionfind
{
	vi arr;
	void init(int _size)
	{
		arr.resize(_size);
		iota(all(arr), 0);
	}
	int find(int a) { return arr[a] = (arr[a] == a) ? a : find(arr[a]); }
	void merge(int a, int b)
	{
		a = find(a);
		b = find(b);
		arr[a] = b;
	}
};
unionfind uf;

void merge(vi &base, vi &add)
{
	if (sz(base) < sz(add))
		swap(base, add);
	for (int x : add)
		base.push_back(x);
	add.clear();
}
void merge(set<int> &base, set<int> &add)
{
	if (sz(base) < sz(add))
		swap(base, add);
	for (int x : add)
		base.insert(x);
	add.clear();
}

void dfs(int v, int &idx)
{
	num[v] = low[v] = idx++;
	st.push(v);
	active[v] = true;

	while (!todo[v].empty())
	{
		while (!todo[v].empty())
		{
			int u = todo[v].back();
			todo[v].pop_back();

			if (num[u] == -1)
				dfs(u, idx);
			if (active[u] && low[u] <= num[v])
				low[v] = min(low[v], low[u]);
		}
		if (low[v] == num[v])
		{
			// start collecting the component
			// poping nodes from the stack
			while (st.top() != v)
			{
				int u = st.top();
				st.pop();
				// todo
				merge(todo[v], todo[u]);
				// nodes
				merge(nodesInC[v], nodesInC[u]);
				// keys
				for (int k : keys[u])
					if (npk[v].find(k) != npk[v].end())
					{
						merge(todo[v], npk[v][k]);
						npk[v].erase(k);
					}
				merge(keys[v], keys[u]);
				// undone edges
				for (auto it : npk[u])
				{
					if (keys[v].find(it.first) != keys[v].end())
						merge(todo[v], it.second);
					else
						merge(npk[v][it.first], it.second);
				}
				npk[u].clear();
			}
		}
	}
	if (low[v] == num[v])
	{
		// finish collecting the component
		// deactivating all nodes
		assert(st.top() == v);
		st.pop();
		for (int u : nodesInC[v])
			active[u] = false;
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c)
{
	N = sz(r), M = sz(u);
	R = r;

	keys.resize(N);
	for (int i = 0; i < N; ++i)
		keys[i].insert(r[i]);

	npk.resize(N);
	todo.resize(N);
	for (int i = 0; i < sz(u); ++i)
	{
		if (R[u[i]] != c[i])
			npk[u[i]][c[i]].push_back(v[i]);
		else
			todo[u[i]].push_back(v[i]);

		if (R[v[i]] != c[i])
			npk[v[i]][c[i]].push_back(u[i]);
		else
			todo[v[i]].push_back(u[i]);
	}

	// tarjan precomputation
	active.assign(N, false);
	nodesInC.resize(N);
	for (int i = 0; i < N; ++i)
		nodesInC[i].push_back(i);
	num.assign(N, -1), low.assign(N, -1);
	int idx = 0;
	for (int i = 0; i < N; ++i)
		if (num[i] == -1)
			dfs(i, idx);

	// gen dag
	int comp = 0;
	vi belongs(N, -1);
	vi size;
	vector<set<int>> KC;
	for (int i = 0; i < N; ++i)
		if (!nodesInC[i].empty())
		{
			KC.push_back(set<int>());
			size.push_back(sz(nodesInC[i]));
			for (int x : nodesInC[i])
				belongs[x] = comp, KC[comp].insert(R[x]);
			++comp;
		}

	vi out(comp, 0);
	for (int i = 0; i < M; ++i)
	{
		if (belongs[u[i]] == belongs[v[i]])
			continue;
		int uu = belongs[u[i]];
		int vv = belongs[v[i]];
		if (KC[uu].find(c[i]) != KC[uu].end())
			++out[uu];
		if (KC[vv].find(c[i]) != KC[vv].end())
			++out[vv];
	}

	// gen anwer
	int mini = N + 1;
	for (int i = 0; i < comp; ++i)
		if (out[i] == 0)
			mini = min(mini, size[i]);

	vi ans(N, 0);
	for (int i = 0; i < N; ++i)
		ans[i] = (out[belongs[i]] == 0 && mini == size[belongs[i]]);

	return ans;
}

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