Submission #986418

#	Time	Username	Problem	Language	Result	Execution time	Memory
986418		Pyqe	Keys (IOI21_keys)	C++17	100 / 100	955 ms	403600 KiB

keys

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

const long long inf=1e18;
long long n,m,nm=0,a[300069],dsu[300069],cc[300069],dh[300069],mdh[300069],vtd2[300069],cc2[300069];
multiset<long long> ms[300069];
multiset<pair<long long,long long>> el[300069];
queue<long long> al[300069];
bitset<300069> vtd,spc;
pair<long long,long long> ed[600069];

long long fd(long long x)
{
	if(dsu[x]!=x)
	{
		dsu[x]=fd(dsu[x]);
	}
	return dsu[x];
}

inline void jo(long long x,long long y)
{
	long long k,l;
	multiset<long long>::iterator it;
	multiset<pair<long long,long long>>::iterator it2;
	
	x=fd(x);
	y=fd(y);
	if(cc[y]>cc[x])
	{
		swap(x,y);
	}
	mdh[x]=min(mdh[x],mdh[y]);
	vtd2[x]+=vtd2[y];
	for(it=ms[y].begin();it!=ms[y].end();it++)
	{
		k=*it;
		for(it2=el[x].lower_bound({k,0});it2!=el[x].end()&&it2->fr==k;)
		{
			al[x].push(it2->sc);
			it2++;
			el[x].erase(prev(it2));
		}
		ms[x].insert(k);
	}
	for(it2=el[y].begin();it2!=el[y].end();it2++)
	{
		k=it2->fr;
		l=it2->sc;
		if(ms[x].find(k)==ms[x].end())
		{
			el[x].insert(*it2);
		}
		else
		{
			al[x].push(l);
		}
	}
	for(;!al[y].empty();al[y].pop())
	{
		al[x].push(al[y].front());
	}
	cc[x]+=cc[y];
	dsu[y]=x;
}

void scc(long long x)
{
	long long l;
	
	vtd[x]=1;
	vtd2[x]++;
	mdh[x]=dh[x];
	for(;!al[fd(x)].empty();)
	{
		l=al[fd(x)].front();
		al[fd(x)].pop();
		nm++;
		ed[nm]={x,l};
		if(!vtd[l])
		{
			dh[l]=dh[x]+1;
			scc(l);
		}
		if(vtd2[fd(l)]&&mdh[fd(l)]<mdh[fd(x)])
		{
			jo(x,l);
		}
	}
	vtd2[fd(x)]--;
}

vector<int> find_reachable(vector<int> oa,vector<int> ka,vector<int> la,vector<int> wg)
{
	long long i,ii,k,l,w,mn=inf,z;
	vector<int> v;
	
	n=oa.size();
	for(i=1;i<=n;i++)
	{
		a[i]=oa[i-1]+1;
		dsu[i]=i;
		cc[i]=1;
		ms[i].insert(a[i]);
	}
	m=ka.size();
	for(i=0;i<m;i++)
	{
		k=ka[i]+1;
		l=la[i]+1;
		w=wg[i]+1;
		for(ii=0;ii<2;ii++)
		{
			if(a[k]!=w)
			{
				el[k].insert({w,l});
			}
			else
			{
				al[k].push(l);
			}
			cc[k]++;
			swap(k,l);
		}
	}
	for(i=1;i<=n;i++)
	{
		if(!vtd[i])
		{
			dh[i]=0;
			scc(i);
		}
	}
	for(i=1;i<=nm;i++)
	{
		k=ed[i].fr;
		l=ed[i].sc;
		if(fd(k)!=fd(l))
		{
			spc[fd(k)]=1;
		}
	}
	for(i=1;i<=n;i++)
	{
		cc2[fd(i)]++;
	}
	for(i=1;i<=n;i++)
	{
		if(fd(i)==i&&!spc[i])
		{
			mn=min(mn,cc2[i]);
		}
	}
	for(i=1;i<=n;i++)
	{
		z=cc2[fd(i)]==mn&&!spc[fd(i)];
		v.push_back(z);
	}
	return v;
}

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