Submission #438166

#	Time	Username	Problem	Language	Result	Execution time	Memory
438166		mango_lassi	Keys (IOI21_keys)	C++17	0 / 100	1 ms	332 KiB

keys

#include <vector>
#include <bits/stdc++.h>
using namespace std;

class DSU {
	private:
		vector<int> comp, siz;
	public:
		DSU(int n) : comp(n), siz(n, 1) {
			for (int i = 0; i < n; ++i) comp[i] = i;
		}
		int getc(int i) {
			if (comp[i] != i) comp[i] = getc(comp[i]);
			return comp[i];
		}
		bool join(int a, int b) {
			a = getc(a);
			b = getc(b);
			if (a == b) return false;

			if (siz[a] < siz[b]) swap(a, b);
			siz[a] += siz[b];
			comp[b] = a;
			return true;
		}
		int compSize(int i) { return siz[getc(i)]; }
};

struct Targets {
	set<int> act_outs, keys;
	set<pair<int, int>> outs;
};

void merge(int i, int t, DSU& dsu, vector<Targets>& tar) {
	i = dsu.getc(i);
	t = dsu.getc(t);
	dsu.join(i, t);

	// Join smaller to larger
	int si = tar[i].keys.size() + tar[i].outs.size() + tar[i].act_outs.size();
	int st = tar[t].keys.size() + tar[t].outs.size() + tar[t].act_outs.size();
	if (si < st) swap(si, st);

	// Add new keys
	for (int key : tar[t].keys) {
		auto it = tar[i].outs.lower_bound(make_pair(key, 0));
		while(it != tar[i].outs.end() && (*it).first == key) {
			tar[i].act_outs.insert((*it).second);
			auto tmp = it;
			++it;
			tar[i].outs.erase(tmp);
		}
		tar[i].keys.insert(key);
	}

	// Add new edges
	for (int out : tar[t].act_outs) tar[i].act_outs.insert(out);
	for (auto pr : tar[t].outs) {
		auto it = tar[i].keys.find(pr.first);
		if (it != tar[i].keys.end()) tar[i].act_outs.insert(pr.second);
		else tar[i].outs.insert(pr);
	}

	tar[t].act_outs.clear();
	tar[t].keys.clear();
	tar[t].outs.clear();
}

int dfs(int i, vector<int>& state, DSU& dsu, vector<Targets>& tar) {
	state[i] = 1; // Active
	while(true) {
		i = dsu.getc(i);
		if (tar[i].act_outs.empty()) {
			state[i] = -1; // Done, potential smallest
			return -1;
		}

		auto it = tar[i].act_outs.begin();
		int t = dsu.getc(*it);
		tar[i].act_outs.erase(it);

		if (t == i) continue;
		if (state[t] < 0) {
			state[i] = -2; // Done, NOT potential smallest
			return -1;
		} else if (state[t] == 1) {
			return t; // Compress cycle
		}

		int sub = dfs(t, state, dsu, tar);
		if (sub >= 0) {
			bool rec = (dsu.getc(sub) != dsu.getc(i));
			merge(i, t, dsu, tar);
			if (rec) return sub;
		} else {
			state[i] = -2; // Done, NOT potential smallest
			return -1;
		}
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	int m = u.size();

	vector<Targets> tar(n);
	for (int i = 0; i < n; ++i) tar[i].keys.insert(r[i]);
	for (int j = 0; j < m; ++j) {
		if (c[j] == r[u[j]]) tar[u[j]].act_outs.insert(v[j]);
		else tar[u[j]].outs.emplace(c[j], v[j]);
	
		if (c[j] == r[v[j]]) tar[v[j]].act_outs.insert(u[j]);
		else tar[v[j]].outs.emplace(c[j], u[j]);
	}

	DSU dsu(n);
	vector<int> state(n, 0);
	for (int i = 0; i < n; ++i) {
		if (state[dsu.getc(i)] == 0) dfs(i, state, dsu, tar);
	}
	
	vector<pair<int, int>> ord(n);
	for (int i = 0; i < n; ++i) ord[i] = {state[dsu.getc(i)] == -1 ? dsu.compSize(i) : n + 1, i};
	sort(ord.begin(), ord.end());

	vector<int> res(n, 0);
	for (int i = 0; i < n; ++i) res[ord[i].second] |= (ord[i].first == ord[0].first);
	return res;
}

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