Submission #1053022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053022		noyancanturk	Keys (IOI21_keys)	C++17	9 / 100	299 ms	130388 KiB

keys

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
using pii=pair<int,int>;

const int lim=3e5+100;
int n,m;
pii edges[lim];
int cnt[lim];
int parent[lim],sz[lim];
unordered_set<int>havekeys[lim];
unordered_map<int,vector<int>>could[lim];
queue<int>q;
bool disabled[lim];

int find(int i){
	if(parent[i]==i)return i;
	return parent[i]=find(parent[i]);
}
void unite(int i,int j){
	i=find(i),j=find(j);
	if(i^j){
		if(sz[i]<sz[j])swap(i,j);
		parent[j]=i;
		sz[i]+=sz[j];
		vector<int>todel;
		if(havekeys[i].size()<could[j].size()){
			for(int k:havekeys[i]){
				if(could[j].count(k)){
					for(int e:could[j][k]){
						if((++cnt[e])==2){
							q.push(e);
						}
					}
					todel.pb(k);
				}
			}
		}else{
			for(auto&[k,v]:could[j]){
				if(havekeys[i].count(k)){
					for(int e:v){
						if((++cnt[e])==2){
							q.push(e);
						}
					}
					todel.pb(k);
				}
			}
		}
		if(havekeys[j].size()<could[i].size()){
			for(int k:havekeys[j]){
				if(could[i].count(k)){
					for(int e:could[i][k]){
						if((++cnt[e])==2){
							q.push(e);
						}
					}
					todel.pb(k);
				}
			}
		}else{
			for(auto&[k,v]:could[i]){
				if(havekeys[j].count(k)){
					for(int e:v){
						if((++cnt[e])==2){
							q.push(e);
						}
					}
					todel.pb(k);
				}
			}
		}
		for(int i:todel){
			could[i].erase(i);
			could[j].erase(i);
		}
		if(havekeys[i].size()<havekeys[j].size())swap(havekeys[j],havekeys[i]);
		for(int k:havekeys[j]){
			havekeys[i].insert(k);
		}
		havekeys[j].clear();
		if(could[i].size()<could[j].size())swap(could[j],could[i]);
		for(auto&[k,v]:could[j]){
			if(could[i].count(k)){
				auto&u=could[i][k];
				if(u.size()<v.size())swap(u,v);
				for(int e:v){
					u.pb(e);
				}
			}
		}
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n=r.size(),m=u.size();
	for(int i=0;i<n;i++){
		parent[i]=i;
		sz[i]=1;
		havekeys[i].insert(r[i]);
	}
	for(int i=0;i<m;i++){
		edges[i]={u[i],v[i]};
		could[u[i]][c[i]].pb(i);
		if(r[u[i]]==c[i]){
			cnt[i]++;
			could[u[i]].erase(c[i]);
		}
		could[v[i]][c[i]].pb(i);
		if(r[v[i]]==c[i]){
			cnt[i]++;
			could[v[i]].erase(c[i]);
		}
		if(cnt[i]==2){
			q.push(i);
		}
	}
	while(q.size()){
		int i=q.front();
		q.pop();
		//cerr<<"uniting "<<u[i]<<" "<<v[i]<<"\n";
		unite(u[i],v[i]);
	}
	for(int i=0;i<m;i++){
			assert(cnt[i]<=2);
		if(cnt[i]==1){
			//cerr<<"edge "<<u[i]<<" "<<v[i]<<"\n";
			u[i]=find(u[i]),v[i]=find(v[i]);
			/*
			cerr<<"keys of "<<u[i]<<": ";
			for(int i:havekeys[u[i]]){
				cerr<<i<<" ";
			}cerr<<"\n";
			cerr<<"keys of "<<v[i]<<": ";
			for(int i:havekeys[v[i]]){
				cerr<<i<<" ";
			}cerr<<"\n";
			*/
			if(havekeys[u[i]].count(c[i])){
				disabled[u[i]]=1;
			}else if(havekeys[v[i]].count(c[i])){
				disabled[v[i]]=1;
			}else{
				assert(0);
			}
		}
	}
	int res=INT_MAX;
	vector<int>ans;
	for(int i=0;i<n;i++){
		int j=find(i);
		/*
		cerr<<i<<" is in "<<j<<"\n";
		cerr<<j<<" is ";
		if(disabled[j])cerr<<"disabled\n";
		else cerr<<"not disabled\n";
		*/
		if(!disabled[j]&&sz[j]<res){
			res=sz[j];
			ans.clear();
		}
		if(!disabled[j]&&res==sz[j]){
			ans.pb(i);
		}
	}
	vector<int>finalans(n,0);
	for(int i:ans){
		finalans[i]=1;
	}
	return finalans;
}

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