Submission #615600

#	Time	Username	Problem	Language	Result	Execution time	Memory
615600		SeDunion	Keys (IOI21_keys)	C++17	100 / 100	1175 ms	120244 KiB

keys

#include "keys.h"
#include <iostream>
#include <vector>
#include <set>

using namespace std;
using vi = vector<int>;

const int N = 300'005;

set<int>keys[N];
set<pair<int,int>>maybe[N];
vector<int>ac[N];

int tree[N];
int gtree(int x) { if (x == tree[x]) return x; return tree[x] = gtree(tree[x]); }

int cc[N];
int gcc(int x) { if (x == cc[x]) return x; return cc[x] = gcc(cc[x]); }

int par[N];

void add_edge(int x, int y) { tree[x] = par[x] = y; }

vector<pair<int,int>>del;

void unite(int x, int y) {
	x = gcc(x), y = gcc(y);
	if (x == y) return;
	if (keys[x].size() + maybe[x].size() + ac[x].size() >
		keys[y].size() + maybe[y].size() + ac[y].size()) swap(x, y);
	cc[x] = y;
	for (auto u : ac[x]) ac[y].emplace_back(u);
	ac[x].clear();
	for (auto u : keys[x]) {
		if (keys[y].count(u)) continue;
		auto it = maybe[y].lower_bound({u, -1});
		while (it != maybe[y].end() && it->first == u) {
			del.emplace_back(*it);
			ac[y].emplace_back(it->second);
			++it;
		}
		keys[y].insert(u);
	}
	for (auto i : del) maybe[y].erase(i); del.clear();
	keys[x].clear();
	for (auto it : maybe[x]) {
		if (keys[y].count(it.first)) ac[y].emplace_back(it.second);
		else maybe[y].insert(it);
	}
	maybe[x].clear();
}

void collapse(int x, int y) {
	while (x != y) {
		unite(x, y);
		y = par[y];
	}
	int a = gtree(gcc(x)), b = gcc(x);
	tree[b] = tree[a] = b;
}

void push(int v) {
	v = gtree(gcc(v));
	while (ac[v].size()) {
		int t = ac[v].back(); ac[v].pop_back();
		t = gcc(t);
		if (v == t) continue;
		int tv = gtree(v);
		int tt = gtree(t);
		if (tv != tt) {
			add_edge(v, tt);
			push(t);
			return;
		}
		// cycle
		collapse(v, t);
		push(v);
		return;
	}
}

vi norm(int n, vi a) {
	vi r(n);
	for (int i : a) r[i] = 1;
	return r;
}

vi find_reachable(vi r, vi u, vi v, vi c) {
	int n = r.size();
	int m = u.size();
	vi ans;
	for (int i = 0 ; i < n ; ++ i) {
		tree[i] = cc[i] = par[i] = i;
	}
	for (int i = 0 ; i < m ; ++ i) {
		maybe[u[i]].insert({c[i], v[i]});
		maybe[v[i]].insert({c[i], u[i]});
	}
	for (int i = 0 ; i < n ; ++ i) {
		keys[i].insert(r[i]);
		auto it = maybe[i].lower_bound({r[i], -1});
		while (it != maybe[i].end() && it->first == r[i]) ac[i].emplace_back(it->second), it++;
		if (ac[i].empty()) ans.emplace_back(i);
	}
	if (ans.size()) return norm(n, ans);
	for (int i = 0 ; i < n ; ++ i) {
		push(i);
	}
	vi cnt(n);
	for (int i = 0 ; i < n ; ++ i) {
		int x = gcc(i);
		if (x == gtree(x)) cnt[x]++;
		else cnt[x] = N;
	}
	int mn = N;
	for (int i = 0 ; i < n ; ++ i) {
		int x = gcc(i);
		mn = min(mn, cnt[x]);
	}
	for (int i = 0 ; i < n ; ++ i) {
		int x = gcc(i);
		if (cnt[x] == mn) ans.emplace_back(i);
	}
	return norm(n, ans);
}

Compilation message (stderr)

keys.cpp: In function 'void unite(int, int)':
keys.cpp:45:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   45 |  for (auto i : del) maybe[y].erase(i); del.clear();
      |  ^~~
keys.cpp:45:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   45 |  for (auto i : del) maybe[y].erase(i); del.clear();
      |                                        ^~~

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