Submission #435789

#	Time	Username	Problem	Language	Result	Execution time	Memory
435789		errorgorn	Keys (IOI21_keys)	C++17	100 / 100	2003 ms	178024 KiB

keys

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
 
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
 
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n,m;
int typ[300005];
set<int> keys[300005];
set<ii> al[300005];
vector<int> proc[300005];

int nxt[300005];

struct UFDS{
	int p[300005];
	int s[300005];
	
	UFDS(){
		rep(x,0,300005){
			p[x]=x;
			s[x]=1;
		}
	}
	
	int parent(int i){
		if (i==p[i]) return i;
		else return p[i]=parent(p[i]);
	}
	
	void unions(int i,int j){
		i=parent(i),j=parent(j);
		if (i==j) return;
		p[i]=j;
		s[j]+=s[i];
	}
} roots,connected;

bool vis[300005];
bool onstk[300005];

void dfs(int i){
	vis[i]=true;
	onstk[i]=true;
	
	if (!vis[nxt[i]]) dfs(nxt[i]);
	else if (onstk[nxt[i]]){
		//merge root cycle
		int curr=nxt[i];
		do{
			roots.unions(curr,i);
			
			if (sz(keys[i])<sz(keys[curr])) swap(keys[i],keys[curr]);
			for (auto &it:keys[curr]) keys[i].insert(it);
			
			if (sz(al[i])<sz(al[curr])) swap(al[i],al[curr]);
			for (auto &it:al[curr]) al[i].insert(it);
			
			if (sz(proc[i])<sz(proc[curr])) swap(proc[i],proc[curr]);
			for (auto &it:proc[curr]) proc[i].pub(it);
			
			curr=nxt[curr];
		} while (curr!=i);
		
		for (auto &it:keys[i]){
			while (true){
				auto iter=al[i].lb(ii(it,-1));
				if (iter!=al[i].end() && (*iter).fi==it){
					proc[i].pub((*iter).se);
					al[i].erase(iter);
				}
				else break;
			}
		}
		
		while (!proc[i].empty()){
			int u=proc[i].back(); proc[i].pob();
			
			if (connected.parent(u)!=connected.parent(i)){ //another forest
				nxt[i]=u;
				connected.unions(i,u);
				break;
			}
			
			while (roots.parent(u)!=roots.parent(i)){
				//if (typ[u]) cout<<"wtf: "<<u<<" "<<typ[u]<<endl;
				
				if (sz(keys[i])+sz(al[i])<sz(keys[u])+sz(al[u])){
					swap(keys[i],keys[u]);
					swap(al[i],al[u]);
				}
				
				for (auto &it:keys[u]){
					while (true){
						auto iter=al[i].lb(ii(it,-1));
						if (iter!=al[i].end() && (*iter).fi==it){
							proc[i].pub((*iter).se);
							al[i].erase(iter);
						}
						else break;
					}
					keys[i].insert(it);
				}
				
				for (auto &it:al[u]){
					if (keys[i].count(it.fi)){
						proc[i].pub(it.se);
					}
					else{
						al[i].insert(it);
					}
				}
				
				if (sz(proc[i])<sz(proc[u])) swap(proc[i],proc[u]);
				for (auto &it:proc[u]) proc[i].pub(it);
				
				roots.unions(u,nxt[u]);
				u=roots.parent(u);
			}
		}
	}
	
	onstk[i]=false;
}

std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	n=sz(R),m=sz(U);
 
	rep(x,0,n){
		typ[x]=R[x];
		keys[x].insert(R[x]);
	}
	
	rep(x,0,m){
		al[U[x]].insert(ii(C[x],V[x]));
		al[V[x]].insert(ii(C[x],U[x]));
	}
	
	memset(nxt,-1,sizeof(nxt));
	rep(x,0,n){
		for (auto &it:al[x]) if (it.fi==typ[x]) nxt[x]=it.se;
	}
	
	bool trivial=false;
	rep(x,0,n) if (nxt[x]==-1) trivial=true;
	
	if (trivial){
		vector<int> ans(n,0);
		rep(x,0,n) if (nxt[x]==-1) ans[x]=1;
		return ans;
	}
	
	rep(x,0,n) connected.unions(x,nxt[x]);
	
	//rep(x,0,n) cout<<nxt[x]<<" "; cout<<endl;
	
	rep(x,0,n){
		while (true){
			auto iter=al[x].lb(ii(typ[x],-1));
			if (iter!=al[x].end() && (*iter).fi==typ[x]){
				proc[x].pub((*iter).se);
				al[x].erase(iter);
			}
			else break;
		}
	}
	
	rep(x,0,n) if (!vis[x]) dfs(x);
	
	int best=1e9;
	set<int> best_roots;
	
	rep(x,0,n){
		if (roots.parent(x)==x && roots.parent(x)==roots.parent(nxt[x])){
			if (best>roots.s[x]) best=roots.s[x],best_roots.clear();
			if (best==roots.s[x]) best_roots.insert(x);
		}
	}
	
	//for (auto &it:best_roots) cout<<it<<" "; cout<<endl;
	
	vector<int> ans(n,0);
	rep(x,0,n) if (best_roots.count(roots.parent(x))) 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