Submission #1032792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032792		hotboy2703	Keys (IOI21_keys)	C++17	100 / 100	1063 ms	265588 KiB

keys

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 3e5+100;
set <ll> out[MAXN];
set <pll> pot[MAXN];
set <ll> keys[MAXN];
set <ll> all[MAXN];
ll in[MAXN];
ll n;
ll dsu[MAXN];
ll f(ll x){
	if (dsu[x] < 0)return x;
	return (dsu[x] = f(dsu[x]));
}
ll join(ll x,ll y){
	if (dsu[x] > dsu[y])swap(x,y);
	dsu[x] += dsu[y];
	dsu[y] = x;
	for (auto z:all[y])out[x].erase(z);
	for (auto z:out[y]){
		if (all[x].find(z) == all[x].end())out[x].insert(z);
	}
	for (auto z:keys[y]){
		for (auto it = pot[x].lower_bound(MP(z,-1));it != pot[x].end() && (*it).fi == z;it = pot[x].erase(it)){
			ll u = (*it).se;
			if (all[x].find(u) == all[x].end() && all[y].find(u) == all[y].end())out[x].insert(u);
		}
	}
	for (auto z:pot[y]){

		if (keys[x].find(z.fi) != keys[x].end()){
			ll u = z.se;
			if (all[x].find(u) == all[x].end() && all[y].find(u) == all[y].end())out[x].insert(u);
		}
		else{
			pot[x].insert(z);
		}
	}
	for (auto z:keys[y])keys[x].insert(z);
	for (auto z:all[y])all[x].insert(z);
	// for (auto z:out[x])assert(all[x].find(z) == all[x].end());
	// for (auto z:pot[x])assert(keys[x].find(z.fi)==keys[x].end());
	return x;
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	n = sz(r);
	std::vector<int> ans(r.size());
	for (ll i = 0;i < n;i ++){
		dsu[i] = -1;
		keys[i] = {r[i]};
		all[i] = {i};
	}
	ll m = sz(u);
	for (ll i = 0;i < m;i ++){
		pot[u[i]].insert(MP(c[i],v[i]));
		pot[v[i]].insert(MP(c[i],u[i]));
	}
	for (ll i = 0;i < n;i ++){
		for (auto it = pot[i].begin();it != pot[i].end();){
			if ((*it).fi == r[i]){
				out[i].insert((*it).se);
				it = pot[i].erase(it);
			}
			else{
				it++;
			}
		}
	}
	for (ll i = 0;i < n;i ++){
		if (!in[i]){
			vector <ll> cur;
			cur.push_back(i);
			in[i] = 1;
			while (true){
				ll u = cur.back();
				// cout<<i<<' '<<u<<endl;
				if (out[u].empty())break;
				ll v = f(*out[u].begin());
				if (in[v]==0){
					in[v]=1;
					cur.push_back(v);
				}
				else{
					if (in[v]==2){
						break;
					}
					else{
						cur.pop_back();
						ll last = u;
						while (cur.back() != v){
							last = join(last,cur.back());
							cur.pop_back();
						}
						last = join(last,cur.back());
						cur.pop_back();
						cur.push_back(last);
					}
				}
			}
			for (auto x:cur)in[x] = 2;
		}
	}
	ll res = n+1;
	for (ll i = 0;i < n;i ++){
		if (dsu[i]<0 && out[i].empty())res = min(res,-dsu[i]);
	}
	for (ll i = 0;i < n;i ++){
		if (out[f(i)].empty() && -dsu[f(i)] == res)ans[i] = 1;
	}
	return ans;
}

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