Submission #1217843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217843		HappyCapybara	Keys (IOI21_keys)	C++17	67 / 100	3093 ms	101840 KiB

keys

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

int n, m;
vector<int> p, t, s, f;
vector<set<int>> keys, unlocked;
vector<set<pair<int,int>>> locked;
vector<bool> done;

int findp(int a){
	if (a == p[a]) return p[a];
	return p[a] = findp(p[a]);
}

int findt(int a){
	if (a == t[a]) return t[a];
	return t[a] = findt(t[a]);
}

void merget(int a, int b){
	a = findt(a);
	b = findt(b);
	if (a != b) t[b] = a;
}

void mergep(int a, int b){
	a = findp(a);
	b = findp(b);
	p[b] = a;
	s[a] += s[b];
	for (int key : keys[a]){
		vector<pair<int,int>> tbe;
		auto it = locked[b].upper_bound({key, -1});
		while (it != locked[b].end() && it->first == key){
			unlocked[b].insert(it->second);
			tbe.push_back(*it);
			it++;
		}
		for (pair<int,int> rip : tbe) locked[b].erase(rip);
	}
	for (int key : keys[b]){
		vector<pair<int,int>> tbe;
		auto it = locked[a].upper_bound({key, -1});
		while (it != locked[a].end() && it->first == key){
			unlocked[a].insert(it->second);
			tbe.push_back(*it);
			it++;
		}
		for (pair<int,int> rip : tbe) locked[a].erase(rip);
	}
	if (keys[a].size() < keys[b].size()) swap(keys[a], keys[b]);
	for (int x : keys[b]) keys[a].insert(x);
	if (unlocked[a].size() < unlocked[b].size()) swap(unlocked[a], unlocked[b]);
	for (int x : unlocked[b]) unlocked[a].insert(x);
	if (locked[a].size() < locked[b].size()) swap(locked[a], locked[b]);
	for (pair<int,int> x : locked[b]) locked[a].insert(x);
}

void solve(int cur){
	//cout << "cur: " << cur << endl;
	if (done[cur]) return;
	done[cur] = true;
	if (cur != findp(cur)) return;
	while (!unlocked[cur].empty()){
		int next = *unlocked[cur].begin();
		unlocked[cur].erase(next);
		if (findp(next) == cur) continue;
		f[cur] = next;
		if (findt(next) != findt(cur)){
			merget(cur, next);
			solve(next);
			return;
		}
		//cout << "cycle: " << next << endl;
		int pt = next;
		while (findp(pt) != cur){
			int pt2 = f[findp(pt)];
			mergep(cur, pt);
			pt = pt2;
		}
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
	n = r.size();
	m = u.size();
	p.resize(n);
	for (int i=0; i<n; i++) p[i] = i;
	t.resize(n);
	for (int i=0; i<n; i++) t[i] = i;
	s.resize(n, 1);
	f.resize(n);
	for (int i=0; i<n; i++) f[i] = i;
	keys.resize(n);
	for (int i=0; i<n; i++) keys[i].insert(r[i]);
	unlocked.resize(n);
	locked.resize(n);
	for (int i=0; i<m; i++){
		if (c[i] == r[u[i]]) unlocked[u[i]].insert(v[i]);
		else locked[u[i]].insert({c[i], v[i]});
		if (c[i] == r[v[i]]) unlocked[v[i]].insert(u[i]);
		else locked[v[i]].insert({c[i], u[i]});
	}
	done.resize(n, false);
	for (int i=0; i<n; i++) solve(i);
	vector<int> res(n, 0);
	int ss = n;
	for (int i=0; i<n; i++){
		if (i == findp(i) && i == findp(f[i])) ss = min(ss, s[i]);
	}
	for (int i=0; i<n; i++){
		if (findp(i) == findp(f[findp(i)]) && s[findp(i)] == ss) res[i] = 1;
	}
	return res;
}

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