Submission #615584

#	Time	Username	Problem	Language	Result	Execution time	Memory
615584		SeDunion	Keys (IOI21_keys)	C++17	37 / 100	3051 ms	367024 KiB

keys

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

#define cerr if(false)cerr

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) {
	cerr << "\t" << x << " -> " << y << " edge\n";
	tree[x] = y;
	par[x] = y;
}

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]) {
		auto it = maybe[y].lower_bound({u, -1});
		while (it != maybe[y].end() && it->first == u) {
			ac[y].emplace_back(it->second);
			++it;
		}
		keys[y].insert(u);
	}
	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) {
	cerr << "\t" << x << " -> " << y << " collapse\n";
	while (x != y) {
		unite(x, y);
		y = par[y];
	}
	int a = gtree(gcc(x));
	int b = gcc(x);
	tree[b] = b;
	tree[a] = b;
	cerr << "\ttree " << a << " -> " << b << endl;
}

void push(int v) {
	v = gcc(v);
	v = gtree(v);
	while (ac[v].size()) {
		int t = ac[v].back(); ac[v].pop_back();
		t = gcc(t);
		int tv = gtree(v);
		int tt = gtree(t);
		if (tv != tt) {
			add_edge(v, tt);
			push(t);
			return;
		}
		// cycle
		collapse(v, t);
		v = gcc(v);
		v = gtree(v);
		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);
	}
	for (int i = 0 ; i < n ; ++ i) {
		cerr << gcc(i) << " "; 
	}
	cerr << endl;
	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) {
		cerr << gtree(gcc(i)) << " ";
	}
	cerr << endl;
	for (int i = 0 ; i < n ; ++ i) {
		cerr << cnt[i] << " ";
	}
	cerr << endl;
	for (int i = 0 ; i < n ; ++ i) {
		int x = gcc(i);
		if (cnt[x] == mn) ans.emplace_back(i);
	}
	return norm(n, ans);
}

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