Submission #832658

#	Time	Username	Problem	Language	Result	Execution time	Memory
832658		Rafi22	Keys (IOI21_keys)	C++17	100 / 100	1071 ms	206744 KiB

keys

#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
     
const int N=300007;

int rep[N];

int Find(int v)
{
	if(rep[v]==v) return v;
	return rep[v]=Find(rep[v]);
}
void Union(int u,int v)
{
	u=Find(u),v=Find(v);
	rep[u]=v;
}

set<int>keys[N];
vector<int>E[N];
set<pair<int,int>>edges[N];
int r[N];
vector<int>X[N];

vector<pair<int,int>>ans;

set<int>Q;

void Merge(int u,int v)
{
	if(sz(X[u])>sz(X[v])) swap(u,v);
	for(auto x:E[u]) E[v].pb(x);
	for(auto x:keys[u])
	{
		keys[v].insert(x);
		while(true)
		{
			pair<int,int>p=*edges[v].lower_bound({x,0});
			if(p.st!=x) break;
			edges[v].erase(p);
			E[v].pb(p.nd);
		}
	}
	for(auto [c,x]:edges[u])
	{
		if(keys[v].count(c)) E[v].pb(x);
		else edges[v].insert({c,x});
	}
	for(auto x:X[u])
	{
		X[v].pb(x);
		r[x]=v;
	}
	while(sz(E[v])>0) 
	{
		if(r[E[v].back()]==v) E[v].pop_back();
		else break;
	}
}

vector<int>find_reachable(vector<int>K,vector<int>U,vector<int>V,vector<int>C)
{
	int n=sz(K),m=sz(U);
	for(int i=0;i<n;i++)
	{
		rep[i]=i;
		X[i].pb(i);
		r[i]=i;
		keys[i].insert(K[i]);
		edges[i].insert({inf,0});
	}
	for(int i=0;i<m;i++)
	{
		if(keys[U[i]].count(C[i]))  E[U[i]].pb(V[i]);
		else edges[U[i]].insert({C[i],V[i]});
		if(keys[V[i]].count(C[i]))  E[V[i]].pb(U[i]);
		else edges[V[i]].insert({C[i],U[i]});
	}
	for(int i=0;i<n;i++) 
	{
		if(sz(E[i])==0) ans.pb({1,i});
		else
		{
			if(Find(i)==Find(E[i].back())) Q.insert(i);
			else Union(i,E[i].back());
		}
	}
	while(sz(Q)>0)
	{
		int v=*Q.begin();
		Q.erase(v);
		int x=v;
		vector<int>C;
		while(true)
		{
			C.pb(x);
			x=r[E[r[x]].back()];
			if(x==v) break;
		}
		for(int i=1;i<sz(C);i++) Merge(r[C[i]],r[C[i-1]]);
		v=r[v];
		if(sz(E[v])>0)
		{
			if(Find(v)==Find(r[E[v].back()])) Q.insert(v);
			else Union(v,r[E[v].back()]);
		}
		else
		{
			for(auto x:X[v]) ans.pb({sz(X[v]),x});
		}
	}
	sort(all(ans));
	vector<int>res(n,0);
	for(auto [k,i]:ans) if(k==ans[0].st) res[i]=1;
	return res;
}
/*
int main()
{
	int n,m;
	cin>>n>>m;
	vector<int>K(n);
	for(int i=0;i<n;i++) cin>>K[i];
	vector<int>U(m),V(m),C(m);
	for(int i=0;i<m;i++) cin>>U[i]>>V[i]>>C[i];
	vector<int>X=find_reachable(K,U,V,C);
	for(auto x:X) cout<<x<<" ";
	cout<<endl;
	return 0;
}*/

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