Submission #438410

#	Time	Username	Problem	Language	Result	Execution time	Memory
438410		mango_lassi	Keys (IOI21_keys)	C++17	100 / 100	2109 ms	120008 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);
			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);
	assert(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(i, t);
	dsu.join(i, t);

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

		/*
		cerr << "dfs(" << i << "): ";
		for (int t : tar[i].act_outs) cerr << t << ' '; cerr << "/ ";
		for (int x : tar[i].keys) cerr << x << ' '; cerr << "/ ";
		for (auto pr : tar[i].outs) cerr << pr.first << "," << pr.second << " "; cerr << "\n";
		*/

		if (tar[i].act_outs.empty()) {
			// cerr << "Done, POTENTIAL SMALLEST\n";
			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);

		// cerr << "Edge " << i << ' ' << t << ": " << state[t] << endl;

		if (t == i) continue;
		if (state[t] < 0) {
			// cerr << "Done, NOT POTENTIAL SMALLEST\n";
			state[i] = -2; // Done, NOT potential smallest
			return -1;
		} else if (state[t] == 1) {
			// cerr << "Found cycle!\n";
			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) {
				// cerr << "Found cycle!\n";
				return sub;
			}
		} else {
			// cerr << "Done, NOT POTENTIAL SMALLEST\n";
			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: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 33 / 33