Submission #873469

#	Time	Username	Problem	Language	Result	Execution time	Memory
873469		1bin	Keys (IOI21_keys)	C++17	0 / 100	17 ms	52316 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);
}

void add_edge(int a, int b, int c){
    vector<ll> tmp;
    if(mp[a].find(c) == mp[a].end()){
        prohibit.push_back(tmp);
		prohibit[base].push_back(b);
        mp[a][c] = base++;
    }
    else prohibit[mp[a][c]].push_back(b);
    return;
}

vector<int> find_reachable(vector<int>R,vector<int>U,vector<int>V,vector<int>C){
	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];
		add_edge(a, b, c);
        add_edge(b, a, c);
	}
    
	vector<ll>flag;
	for(int i=0;i<n;i++){
		key[i].insert(R[i]);
		if(!mp[i][R[i]]){
			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;
	}

    // subtask 1
    // R[i]가 모두 0인 경우만 살아남음
    for(int i = 0; i < n; i++) assert(R[i] == 0);
	//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()){
		x=q.front(); q.pop();
		int nx=go[x].back();
		
		if(--indegree[nx]==0){
			q.push(nx);
			checked[nx]=true;
		}
	}
	for(int i=0;i<n;i++){
		if(checked[i])continue;
		cycle.push_back(i);
	}

	ans=inf;
	vector<ll>root;
	for(auto x:cycle){
		if(checked[x])continue;
		vector<ll>T;
		T.push_back(x);
		checked[x]=true;

		int y = go[x].back();
		while(!checked[y]){
			T.push_back(y);
			checked[y]=true;
			y= go[y].back();
		}

		assert(x==y);
		ll tmp=T[0];
		for(auto nxt:T) merge(tmp,nxt);
		root.push_back(find(x));
	}
	
	while(root.size()){
		a=root.back(); root.pop_back();

		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);
				
				root.push_back(find(a));
			}
			else{
				merge2(a,go[a].back());
			}
		}
		else{
            Y[a] = 1;
			ans=min(ans,sz[a]);
		}
	}
    assert(ans < inf);
	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