Submission #828788

#	Time	Username	Problem	Language	Result	Execution time	Memory
828788		fatemetmhr	Keys (IOI21_keys)	C++17	100 / 100	1712 ms	216760 KiB

keys

// Be Name Khoda //

//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair

const int maxn5 = 3e5 + 10;

set <int> key[maxn5];
set <pair<int, int>> ed[maxn5];
vector <int> edge[maxn5], av[maxn5];
vector <pair<int, int>> adj[maxn5];
int cmp[maxn5], r[maxn5], mark[maxn5];
bool bad[maxn5];

int merge(int a, int b){
	if(av[a].size() < av[b].size())
		swap(a, b);
	//cout << "here merging " << a << ' ' << b << endl;
	for(auto u : av[b]){
		cmp[u] = a;
		av[a].pb(u);
		key[r[u]].insert(a);
		for(auto it = ed[r[u]].lower_bound(mp(a, -1)); it != ed[r[u]].end() && (it -> fi) == a;){
			auto itt = it;
			it++;
			edge[a].pb(itt -> se);
			ed[r[u]].erase(itt);
		}
		for(auto [v, c] : adj[u]){
			if(key[c].find(a) != key[c].end())
				edge[a].pb(v);
			else
				ed[c].insert({a, v});
		}
	}
	av[b].clear();
	av[b].shrink_to_fit();
	return a;
}

bool dfs(int v){
	mark[v] = 1;
	//debug(v);
	while(edge[v].size()){
		int u = edge[v].back();
		u = cmp[u];
		//cout << "here is " << v << ' ' << u << ' ' << mark[u] << endl;
		edge[v].pop_back();
		if(u == v)
			continue;
		if(mark[u] == 0){
			if(dfs(u)){
				v = merge(v, cmp[u]);
				mark[v] = 1;
			}
			else{
				bad[v] = true;
				mark[v] = 2;
				return false;
			}
		}
		else if(mark[u] == 1){
			edge[v].pb(u);
			return true;
		}
		else{
			bad[v] = true;
			mark[v] = 2;
			return false;
		}
	}
	mark[v] = 2;
	return false;
}


std::vector<int> find_reachable(std::vector<int> R, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	
	int n = R.size();
	for(int i = 0; i < n; i++){
		r[i] = R[i];
		key[r[i]].insert(i);
		cmp[i] = i;
		av[i].pb(i);
	}
	for(int i = 0; i < int(u.size()); i++){
		adj[u[i]].pb({v[i], c[i]});
		adj[v[i]].pb({u[i], c[i]});
		if(r[u[i]] == c[i])
			edge[u[i]].pb(v[i]);
		if(r[v[i]] == c[i])
			edge[v[i]].pb(u[i]);
		ed[c[i]].insert({v[i], u[i]});
		ed[c[i]].insert({u[i], v[i]});
	}
	for(int i = 0; i < n; i++)
		adj[i].shrink_to_fit();

	for(int i = 0; i < n; i++) if(!mark[i])
		dfs(i);
	int mn = n;
	vector <int> good;
	for(int i = 0; i < n; i++) if(cmp[i] == i && !bad[i]){
		//cout << "ha " << i << ' ' << av[i].size() << endl;
		if(int(av[i].size()) < mn){
			good.clear();
			good = av[i];
			mn = av[i].size();
		}
		else if(int(av[i].size()) == mn)
			for(auto u : av[i])
				good.pb(u);
	}

	vector <int> ret;
	ret.resize(n);
	fill(all(ret), 0);
	for(auto u : good)
		ret[u] = true;
	return ret;

}

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