Submission #536241

#	Time	Username	Problem	Language	Result	Execution time	Memory
536241		grt	Keys (IOI21_keys)	C++17	100 / 100	1759 ms	177284 KiB

keys

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

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

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

const int nax = 300 * 1000 + 10, INF = 1e9 + 10;
int n, m;
int type[nax];
map<int, vi>outEdges[nax];
set<int>colors[nax];
set<int>valid[nax];
int par[nax], siz[nax], nxt[nax], par2[nax];
bool done[nax];
queue<int>Q;
int deg[nax];
vi who[nax];

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

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

void Onion(int a, int b) {
	a = Fund(a), b = Fund(b);
	if(a == b) return;
	if((int)who[a].size() < (int)who[b].size()) swap(a, b);
	for(auto it : outEdges[b]) {
		if(colors[a].count(it.ST)) {
			for(int x : it.ND) {
				valid[a].insert(x);
			}
		} else {
			for(int x : it.ND) {
				outEdges[a][it.ST].PB(x);
				siz[a]++;
			}
		}
	}
	for(int x : valid[b]) {
		valid[a].insert(x);
	}
	for(int x : who[b]) {
		who[a].PB(x);
	}
	for(int x : colors[b]) {
		for(int y : outEdges[a][x]) {
			valid[a].insert(y);
		}
		siz[a] -= (int)outEdges[a][x].size();
		outEdges[a][x].clear();
		colors[a].insert(x);
	}
	who[b].clear();
	colors[b].clear();
	valid[b].clear();
	outEdges[b].clear();
	par[b] = a;
}

set<int>roots;

void merge(int x) {
	x = Fund(x);
	int y = x;
	vi ver = {};
	while(Fund(nxt[y]) != x) {
		y = Fund(nxt[y]);
		ver.PB(y);
	}
	for(int z : ver) Onion(z, x);
	roots.insert(x);
}


vi find_reachable(vi _r, vi _u, vi _v, vi _c) {
	n = (int)_r.size();
	for(int i = 0; i < n; ++i) {
		type[i] = _r[i];
	}
	m = (int)_u.size();
	for(int i = 0; i < m; ++i) {
		outEdges[_u[i]][_c[i]].PB(_v[i]);
		outEdges[_v[i]][_c[i]].PB(_u[i]);
		siz[_u[i]]++;
		siz[_v[i]]++;
	}
	vi emptyOut;
	for(int i = 0; i < n; ++i) {
		if((int)outEdges[i][type[i]].size() == 0) {
			emptyOut.PB(i);
		} else {
			nxt[i] = outEdges[i][type[i]].back();
			deg[nxt[i]]++;
			par[i] = i;
			who[i] = {i};
			par2[i] = nxt[i];
			colors[i].insert(type[i]);
			for(int x : outEdges[i][type[i]]) {
				valid[i].insert(x);
			}
			siz[i] -= (int)outEdges[i][type[i]].size();
			outEdges[i][type[i]].clear();
		}
	}
	if((int)emptyOut.size() > 0) {
		vi ans(n);
		fill(ans.begin(), ans.end(), 0);
		for(int x : emptyOut) ans[x] = 1;
		return ans;
	}
	for(int i = 0; i < n; ++i) {
		if(deg[i] == 0) {
			Q.push(i);
		}
	}
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		done[x] = true;
		deg[nxt[x]]--;
		if(deg[nxt[x]] == 0) {
			Q.push(nxt[x]);
		}
	}
	for(int i = 0; i < n; ++i) {
		if(!done[i]) {
			int x = i;
			while(nxt[x] != i) {
				x = nxt[x];
				done[x] = true;
			}
			done[i] = true;
			merge(i);
		}
	}
	vector<vi>reach;
	int ans = INF;
	while(!roots.empty()) {
		int r = *roots.begin();
		roots.erase(r);
		r = Fund(r);
		if(!valid[r].empty()) {
			int x = *valid[r].begin();
			valid[r].erase(x);
			nxt[r] = x;
			if(Fund2(x) != r) {
				par2[r] = x;
				continue;
			}
			merge(r);
		} else {
			// znalazlem nie powiekszalny set
			reach.PB(who[r]);
			ans = min(ans, (int)who[r].size());
		}
	}
	vi res(n);
	fill(res.begin(), res.end(), 0);
	for(auto v : reach) {
		if(ans != (int)v.size()) continue;
		for(int x : v) res[x] = 1;
	}
	return res;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
	//auto p = find_reachable({0, 1, 1, 2, 2, 1, 2},
	//{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
	//{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
	//{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
	//for(int x : p) cout << x << " ";
	//find_reachable({0, 0, 0}, {0}, {1}, {0});
//}

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