Submission #424573

#	Time	Username	Problem	Language	Result	Execution time	Memory
424573		Pyqe	Simurgh (IOI17_simurgh)	C++14	100 / 100	254 ms	8308 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

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

long long n,m,nn=0,nm,dsu[569],ex[569],pr[569],dh[569],sr[569],sq[569],zs=0;
pair<long long,long long> ed[125069],ca[569];
bitset<125069> spc;
vector<pair<long long,long long>> al[569];
bitset<569> vtd,kd,ve;

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

void bd(long long x)
{
	long long i,sz=al[x].size(),l,p;
	
	vtd[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(!vtd[l])
		{
			pr[l]=x;
			dh[l]=dh[x]+1;
			sr[l]=p;
			bd(l);
		}
	}
}

long long qr(long long x,long long w)
{
	long long i,sz=al[x].size(),k,l,p,c=0;
	vector<int> v;
	
	for(i=1;i<=n;i++)
	{
		dsu[i]=i;
	}
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(i<=w&&!vtd[i])
		{
			v.push_back(p-1);
			dsu[fd(l)]=fd(x);
		}
	}
	for(i=1;i<=nn;i++)
	{
		p=ex[i];
		k=ed[p].fr;
		l=ed[p].sc;
		if(fd(k)!=fd(l))
		{
			dsu[fd(l)]=fd(k);
			v.push_back(p-1);
			c+=kd[i];
		}
	}
	return count_common_roads(v)-c;
}

vector<int> find_roads(int on,vector<int> ka,vector<int> la)
{
	long long i,j,k,l,sz,c,mx,lh,rh,md,zz;
	bool bad;
	vector<int> v;
	
	n=on;
	m=ka.size();
	for(i=1;i<=n;i++)
	{
		dsu[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		k=ka[i-1]+1;
		l=la[i-1]+1;
		ed[i]={k,l};
		if(fd(k)!=fd(l))
		{
			dsu[fd(l)]=fd(k);
			nn++;
			ex[nn]=i;
			spc[i]=1;
			al[k].push_back({l,nn});
			al[l].push_back({k,nn});
			v.push_back(i-1);
			kd[nn]=1;
		}
	}
	bd(1);
	c=count_common_roads(v);
	for(i=1;i<=n;i++)
	{
		dsu[i]=i;
		al[i].clear();
	}
	for(i=1;i<=m;i++)
	{
		k=ed[i].fr;
		l=ed[i].sc;
		al[k].push_back({l,i});
		if(!spc[i]&&fd(k)!=fd(l))
		{
			nm=0;
			mx=c;
			bad=0;
			for(;k!=l;k=pr[k])
			{
				if(dh[k]<dh[l])
				{
					swap(k,l);
				}
				if(!ve[sr[k]]||(!kd[sr[k]]&&!bad))
				{
					v.clear();
					for(j=1;j<=nn;j++)
					{
						if(j!=sr[k])
						{
							v.push_back(ex[j]-1);
						}
					}
					v.push_back(i-1);
					nm++;
					ca[nm]={count_common_roads(v),sr[k]};
					mx=max(mx,ca[nm].fr);
					bad|=ve[sr[k]];
					ve[sr[k]]=1;
				}
				dsu[fd(l)]=fd(k);
			}
			for(j=1;j<=nm;j++)
			{
				k=ca[j].fr;
				l=ca[j].sc;
				kd[l]=k<mx;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		vtd.reset();
		sz=al[i].size();
		for(;qr(i,sz-1);)
		{
			for(zz=sz-1,lh=0,rh=sz-2;lh<=rh;)
			{
				md=(lh+rh)/2;
				if(qr(i,md))
				{
					zz=md;
					rh=md-1;
				}
				else
				{
					lh=md+1;
				}
			}
			zs++;
			sq[zs]=al[i][zz].sc;
			vtd[zz]=1;
		}
	}
	v.clear();
	for(i=1;i<=zs;i++)
	{
		v.push_back(sq[i]-1);
	}
	return v;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30