Submission #448741

#	Time	Username	Problem	Language	Result	Execution time	Memory
448741		grt	Keys (IOI21_keys)	C++17	100 / 100	1585 ms	184236 KiB

keys

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10;
int n, m;
vector<pi>V[nax];
int par[nax];
set<int>reach[nax];
int p[nax], deg[nax];
vi vertices[nax];
bool done[nax];
map<int, vi> graph[nax];
vi edges[nax];
int G[nax];

int p2[nax], siz[nax];

int Fund(int x) {
	if(p2[x] != x) p2[x] = Fund(p2[x]);
	return p2[x];
}

bool Onion(int a, int b) {
	a = Fund(a); b = Fund(b);
	if(a == b) return false;
	if(siz[a] < siz[b]) swap(a, b);
	p2[b] = a;
	siz[a] += siz[b];
	return true;
}
	

void merge(int a, int b) {
	if(p[a] == p[b]) return;
	if((int)vertices[p[a]].size() < (int)vertices[p[b]].size()) swap(a, b);
	int pb = p[b];
	if(G[p[a]] < G[pb]) {
		swap(G[p[a]], G[pb]);
		reach[p[a]].swap(reach[pb]);
		graph[pb].swap(graph[p[a]]);
	}
	for(auto &it : graph[pb]) {
		if(reach[p[a]].count(it.ST)) {
			for(int &x : it.ND) {
				edges[p[a]].PB(x);
			}
		} else {
			for(int &x : it.ND) {
				graph[p[a]][it.ST].PB(x);
			}
		}
	}
	G[p[a]] += G[pb];
	graph[pb].clear();
	for(int x : vertices[pb]) {
		p[x] = p[a];
		vertices[p[a]].PB(x);
	}
	for(int x : reach[pb]) {
		if(!reach[p[a]].count(x)) {
			for(int &y : graph[p[a]][x]) {
				edges[p[a]].PB(y);
			}
			graph[p[a]][x].clear();
		}
		reach[p[a]].insert(x);
	}
	if((int)edges[p[a]].size() < (int)edges[pb].size()) edges[p[a]].swap(edges[pb]);
	for(int x : edges[pb]) {
		edges[p[a]].PB(x);
	}
	edges[pb].clear();
	vertices[pb].clear();
	reach[pb].clear();
}

vi find_reachable(vi r, vi u, vi v, vi c) {
	n = (int)r.size();
	m = (int)u.size();
	for(int i = 0; i < m; ++i) {
		V[u[i]].emplace_back(v[i], c[i]);
		V[v[i]].emplace_back(u[i], c[i]);
	}
	vi tmp = {};
	for(int i = 0; i < n; ++i) {
		p2[i] = i; siz[i] = 1;
	}
	for(int i = 0; i < n; ++i) {
		bool any = false;
		for(auto nbh : V[i]) {
			if(r[i] == nbh.ND) {
				par[i] = nbh.ST;
				edges[i].PB(nbh.ST);
				any = true;
			}
			graph[i][nbh.ND].PB(nbh.ST);
		}
		G[i] = (int)V[i].size();
		if(!any) {
			tmp.PB(i);
		}
		reach[i].insert(r[i]);
		vertices[i].PB(i);
		p[i] = i;
		deg[par[i]]++;
		Onion(par[i], i);
	}
	if((int)tmp.size() > 0) {
		vi ans(n);
		for(int x : tmp) ans[x] = true;
		return ans;
	}
	vi zeroDeg = {};
	for(int i = 0; i < n; ++i) {
		if(deg[i] == 0) {
			zeroDeg.PB(i);
		}
	}
	while((int)zeroDeg.size() > 0) {
		int x = zeroDeg.back();
		done[x] = true;
		zeroDeg.pop_back();
		deg[par[x]]--;
		if(deg[par[x]] == 0) zeroDeg.PB(par[x]);
	}
	vi roots;
	for(int i = 0; i < n; ++i) {
		if(!done[i]) {
			vi cycle = {i};
			int x = i;
			done[i] = true;
			while(par[x] != i) {
				x = par[x];
				done[x] = true;
				cycle.PB(x);
			}
			for(int j = 1; j < (int)cycle.size(); ++j) {
				merge(cycle[j - 1], cycle[j]);
			}
			roots.PB(p[i]);
		}
	}
	vector<vi>res;
	while((int)roots.size() > 0) {
		//for(int i = 0; i < n; ++i) {
			//cout << p[i] << " ";
		//}
		//cout << "\n";
		int x = roots.back();
		if(edges[x].size() == 0) {
			res.PB(vertices[x]);
			roots.pop_back();
			continue;
		}
		int y = edges[x].back();
		edges[x].pop_back();
		if(p[x] == p[y]) continue;
		//cout << "MERGING: " << x << " " << y << "\n";
		x = p[x]; y = p[y];
		if(!Onion(x, y)) {
			//cout << "OPT1\n";
			vi path = {y};
			while(p[par[y]] != x) {
				//cerr << p[par[y]] << " " << x << "\n";
				path.PB(p[par[y]]);
				y = p[par[y]];
			}
			path.PB(x);
			for(int j = 1; j < (int)path.size(); ++j) {
				merge(path[j], path[j - 1]);
			}
			roots.pop_back();
			roots.PB(p[path[0]]);
		} else {
			//cout << "OPT2\n";
			par[x] = p[y];
			roots.pop_back();
		}
	}
	int mi = 1000000000;
	for(auto &vec : res) {
		mi = min(mi, (int)vec.size());
	}
	vi ans(n);
	for(int i = 0; i < n; ++i) ans[i] = 0;
	for(auto &vec : res) {
		if((int)vec.size() == mi) {
			for(int x : vec) {
				ans[x] = 1;
			}
		}
	}
	return ans;
}

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