Submission #873471

#	Time	Username	Problem	Language	Result	Execution time	Memory
873471		1bin	Keys (IOI21_keys)	C++17	0 / 100	17 ms	52436 KiB

keys

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ = 3e5 + 505, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans,k;
//shfit + tab 
//ctrl + k + c
ll gcd(ll x, ll y) {
	if (!y)return x;
	return gcd(y, x % y);
};
ll par[n_],to[n_],par2[n_],sz[n_],Y[n_];
vector<P>v[n_];
set<ll>key[n_];
vector<ll>go[n_];
//현재 가지고 있는 키들의 종류
vector<vector<ll>>prohibit;
map<ll,ll>mp[n_];
//갈 수 있는 곳s

ll find(ll x){
    if(par[x]<0)return x;
    return par[x]=find(par[x]);
}
ll find2(ll x){
	if(par2[x]<0)return x;
	return par2[x]=find(par2[x]);
}
void merge2(ll x,ll y){
	x=find2(x),y=find2(y);
	if(x==y)return;
	par2[x]=y;
}
void chk(ll x){
	x=find(x);
	while(go[x].size() && find(x)==find(go[x].back())){
		go[x].pop_back();
	}
}
void merge(ll x,ll y){
    x=find(x),y=find(y);
	if(x==y)return;
	//x is always larger than y
	//
	//if(key[x].size()<key[y].size())swap(x,y);
	for(auto nxt:key[y]){
		if(key[x].find(nxt)==key[x].end()){
			//새로운 key가 들어 왔을 경우
			key[x].insert(nxt);
			if(mp[x].find(nxt)!=mp[x].end()){
				int idx=mp[x][nxt];
				for(auto i:prohibit[idx])go[x].push_back(i);
				prohibit[idx].clear();
				mp[x].erase(nxt);
			}
		}
	}
	for(auto nxt:mp[y]){
		if(key[x].find(nxt.first)==key[x].end()){
			if(mp[x].find(nxt.first)!=mp[x].end()){
				int idx1=mp[x][nxt.first],idx2=nxt.second;

				for(auto i:prohibit[idx2])prohibit[idx1].push_back(i);
				prohibit[idx2].clear();
			}
			else{
				mp[x][nxt.first]=nxt.second;
			}
		}
		else{
			for(auto i:prohibit[nxt.second])go[x].push_back(i);
			prohibit[nxt.second].clear();
		}
	}
	for(auto nxt:go[y])go[x].push_back(nxt);
	mp[y].clear(),go[y].clear();
	par[y]=x;
	sz[x]+=sz[y];
	chk(x);
}
vector<int> find_reachable(vector<int>R,vector<int>U,vector<int>V,vector<int>C){
	vector<ll>tmp;
	n=R.size();
	m=U.size();
    vector<int>ret(n);
	memset(par,-1,sizeof(par));
	memset(par2,-1,sizeof(par2));
	fill(sz,sz+n_,1);
	for(int i=0;i<m;i++){
		a=U[i],b=V[i],c=C[i];
		if(mp[a].find(c)==mp[a].end()){
			mp[a][c]=base;
			prohibit.push_back(tmp);
			prohibit[base].push_back(b);
			base++;
		}
		else prohibit[mp[a][c]].push_back(b);
		if(mp[b].find(c)==mp[b].end()){
			mp[b][c]=base;
			prohibit.push_back(tmp);
			prohibit[base].push_back(a);
			base++;
		}
		else prohibit[mp[b][c]].push_back(a);
	}
	vector<ll>flag;
	for(int i=0;i<n;i++){
		key[i].insert(R[i]);
		if(mp[i].find(R[i])==mp[i].end()){
			flag.push_back(i);
			continue;
		}
		ll index=mp[i][R[i]];
		for(auto nxt:prohibit[index])go[i].push_back(nxt);
		prohibit[index].clear();
		mp[i].erase(R[i]);
	}
	if(flag.size()){
		for(auto nxt:flag)ret[nxt]=1;
		return ret;
	}
	//assert(0);
	//이 케이스는 도착가능한 정점이 자기자신 뿐인 정점이 존재해서, 그 정점이 정답이 될 때.
	//그것이 아니라면 functional graph이기 때문에 scc가 연결 그래프 당 정확히 1개 존재해서 그 정점들을 묶을 수 있다.
	queue<ll>q;
	vector<int>indegree(n),checked(n),cycle;
	for(int i=0;i<n;i++){
		assert(go[i].size());
		merge2(i,go[i].back());
		indegree[go[i].back()]++;
	}
	for(int i=0;i<n;i++){
		if(indegree[i])continue;
		checked[i]=true;
		q.push(i);
	}
	while(q.size()){
		a=q.front();
		q.pop();
		x=go[a].back();
		indegree[x]--;
		if(indegree[x]==0){
			q.push(x);
			checked[x]=true;
		}
	}
	for(int i=0;i<n;i++){
		if(checked[i])continue;
		cycle.push_back(i);
		//cout<<i<<' ';
	}
	ans=inf;
	vector<ll>root;
	for(auto nxt:cycle){
		if(checked[nxt])continue;
		vector<ll>T;
		T.push_back(nxt);
		checked[nxt]=true;
		assert(nxt==find(nxt));
		a=go[nxt].back();
		while(!checked[a]){
			T.push_back(a);
			checked[a]=true;
			a=find(go[a].back());
		}
		assert(a==nxt);
		ll tmp=T[0];
		for(auto nxt:T){
			merge(tmp,nxt);
			//assert(find2(tmp)==find2(nxt));
		}
		a=find(a);
		chk(a);
		root.push_back(a);
	}
	
    // subtask 1
    // R[i]가 모두 0인 경우만 살아남음
    for(int i = 0; i < n; i++) assert(R[i] == 0);
	while(root.size()){
		a=root.back();
		//cout<<"ROOT "<<a<<endl;
		root.pop_back();
		chk(a);
		if(go[a].size()){
			if(find2(a)==find2(go[a].back())){
				vector<ll>T;
				T.push_back(a);
				ll now=find(go[a].back());
				while(1){
					T.push_back(now);
					now=find(go[now].back());
					if(a==now)break;
				}
				for(auto nxt:T)merge(a,nxt);
				a=find(a);
				chk(a);
				root.push_back(a);
			}
			else{
				merge2(a,go[a].back());
			}
		}
		else{
            Y[a] = 1;
			ans=min(ans,sz[a]);
		}
	}
	for(int i=0;i<n;i++){
		if(!Y[find(i)] || sz[find(i)]!=ans)continue;
		ret[i]=1;
	}
    return ret;
}

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