Submission #1048141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048141		Edu175	Keys (IOI21_keys)	C++17	100 / 100	920 ms	119836 KiB

keys

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fjhg:v)cout<<fjhg<<" ";cout<<"\n";}
using namespace std;
typedef int ll;
typedef pair<ll,ll> ii;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
const ll MAXN=3e5+5;


ll uf[MAXN];
vector<ll>nxt[MAXN];
set<ll>col[MAXN];
map<ll,vector<ll>>mp[MAXN];
ll find(ll x){return uf[x]<0?x:uf[x]=find(uf[x]);}
void join(ll x, ll y){
	x=find(x),y=find(y);
	if(x==y)return;
	if(uf[x]>uf[y])swap(x,y);
	uf[x]+=uf[y]; uf[y]=x;

	if(SZ(nxt[x])<SZ(nxt[y]))swap(nxt[x],nxt[y]);
	for(auto i:nxt[y])nxt[x].pb(i);; nxt[y].clear();
	
	if(sizeof(col[x])+sizeof(mp[x])<sizeof(col[y])+sizeof(mp[y])){
		swap(col[x],col[y]);
		swap(mp[x],mp[y]);
		
	}
	// if(sizeof(mp[x])<sizeof(mp[y]))swap(mp[x],mp[y]);
	for(auto i:col[y]){
		col[x].insert(i);
		for(auto j:mp[x][i])nxt[x].pb(j);
		mp[x][i].clear();
	}
	col[y].clear();
	for(auto &[c,v]:mp[y]){
		auto &u=mp[x][c];
		// if(SZ(u)<SZ(v))swap(u,v);
		ll flag=col[x].count(c);
		for(auto i:v){
			if(flag)nxt[x].pb(i);
			else u.pb(i);
		}
		v.clear();
	}
	mp[y].clear();
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
	ll n=SZ(r);
	mset(uf,-1);
	vector<ll>viv(n,-1);
	fore(i,0,n)col[i]={r[i]};
	auto add_edge=[&](ll u, ll v, ll c){
		if(r[u]==c)nxt[u].pb(v);
		else mp[u][c].pb(v);
	};
	fore(i,0,SZ(u)){
		add_edge(u[i],v[i],c[i]);
		add_edge(v[i],u[i],c[i]);
	}
	auto fin=[&](ll x, auto &&fin)->ll{
		x=find(x);
		return viv[x]==-1?x:viv[x]=fin(viv[x],fin);};
	auto get=[&](ll x){
		x=find(x);
		auto r=fin(x,fin);
		return x==r?-1:r;
	};
	fore(i,0,n){
		// cout<<i<<":\n";
		while(SZ(nxt[find(i)])){
			auto x=find(i),j=nxt[x].back(),y=find(j);
			// cout<<x<<": ";
			// fore(i,0,n)if(find(i)==find(x))cout<<i<<" ";
			// cout<<"\n";
			// cout<<"col ";;for(auto i:col[x])cout<<i<<" ";;cout<<"\n\n";
			
			if(x==y){
				nxt[x].pop_back();
				continue;
			}
			if(get(y)!=-1&&get(y)==x){
				viv[y]=-1;
				nxt[x].pop_back();
				join(x,y);
			}
			else{
				viv[x]=y;
				break;
			}
			
		}
		// cout<<i<<": "<<viv[i]<<"\n";
	}
	
	ll res=n+5;
	vector<vector<ll>>cand(n+1);
	fore(x,0,n)if(viv[find(x)]==-1){
		ll q=-uf[find(x)];
		cand[q].pb(x);
		res=min(res,q);
	}
	// cout<<res<<endl;
	vector<int>ret(n);
	for(auto i:cand[res])ret[i]=1;
	return ret;
}

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