Submission #244356

#	Time	Username	Problem	Language	Result	Execution time	Memory
244356		MvC	Collapse (JOI18_collapse)	C++11	5 / 100	15089 ms	16476 KiB

collapse

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "collapse.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mg=5000;
const ll mod=1e9+7;
using namespace std;
int n,c,q,t,i,j,x,y,ai,bi,er,p[nmax],sz[nmax],v[nmax];
vector<pair<pair<int,int>,pair<int,int> > >rl,ed[nmax],vc,a,b;
vector<pair<pair<int,int>,int> >qr[nmax];
set<pair<int,int> >s;
vector<int>rs;
set<pair<int,int> >::iterator it;
int fnd(int x)
{
	if(p[x]==x)return x;
	return p[x]=fnd(p[x]);
}
void uni(int x,int y,int k)
{
	x=fnd(x),y=fnd(y);
	if(x==y)return;
	if(sz[x]<sz[y])swap(x,y);
	if(k)rl.pb(mkp(mkp(y,p[y]),mkp(x,sz[x])));
	p[y]=x;
	sz[x]+=sz[y];
	er++;
}
vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P) 
{
	n=N,c=lun(T),q=lun(W);
	for(i=0;i<c;i++)
	{
		t=T[i],x=X[i],y=Y[i];
		x++,y++;
		if(y>x)swap(x,y);
		ed[i/mg].pb(mkp(mkp(x,y),mkp(t,i)));
	}
	for(i=0;i<q;i++)
	{
		x=W[i],y=P[i];
		y++;
		qr[x/mg].pb(mkp(mkp(y,x%mg),i));
	}
	rs.resize(q,0);
	for(i=0;i<=c/mg;i++)
	{
		if(qr[i].empty())break;
		sort(all(qr[i]));
		for(j=1;j<=n;j++)
		{
			p[j]=j;
			sz[j]=1;
		}
		for(j=0;j<c;j++)
		{
			v[j]=0;
		}
		vc.clear(),a.clear(),b.clear();
		for(j=0;j<i;j++)for(t=0;t<lun(ed[j]);t++)vc.pb(ed[j][t]);
		sort(all(vc));
		for(j=0;j<lun(vc);j++)
		{
			v[vc[j].sc.sc]^=1;
		}
		for(j=0;j<lun(ed[i]);j++)
		{
			if(v[ed[i][j].sc.sc])
			{
				b.pb(ed[i][j]);
				v[ed[i][j].sc.sc]=0;
			}
		}
		for(j=0;j<lun(vc);j++)if(v[vc[j].sc.sc])a.pb(vc[j]),v[vc[j].sc.sc]=0;
		ai=0;
		er=0;
		for(j=0;j<lun(qr[i]);j++)
		{
			for(;ai<lun(a);ai++)
			{
				if(a[ai].fr.fr>qr[i][j].fr.fr)break;
				uni(a[ai].fr.fr,a[ai].fr.sc,0);
			}
			s.clear();
			for(bi=0;bi<lun(b);bi++)
			{
				if(b[bi].fr.fr>qr[i][j].fr.fr)break;
				s.in(b[bi].fr);
			}
			for(t=0;t<=qr[i][j].fr.sc;t++)
			{
				if(ed[i][t].fr.fr>qr[i][j].fr.fr)continue;
				if(s.fd(ed[i][t].fr)!=s.end())s.er(s.fd(ed[i][t].fr));
				else s.in(ed[i][t].fr);
			}
			rl.clear();
			for(it=s.begin();it!=s.end();it++)uni(it->fr,it->sc,1);
			rs[qr[i][j].sc]=qr[i][j].fr.fr-er;
			reverse(all(rl));
			for(t=0;t<lun(rl);t++)
			{
				p[rl[t].fr.fr]=rl[t].fr.sc;
				sz[rl[t].sc.fr]=rl[t].sc.sc;
			}
			er-=lun(rl);
		}
		for(j=1;j<=n;j++)
		{
			p[j]=j;
			sz[j]=1;
		}
		for(j=0;j<lun(a);j++)swap(a[j].fr.fr,a[j].fr.sc);
		for(j=0;j<lun(b);j++)swap(b[j].fr.fr,b[j].fr.sc);
		sort(all(a));
		sort(all(b));
		reverse(all(a));
		reverse(all(b));
		reverse(all(qr[i]));
		ai=0;
		er=0;
		for(j=0;j<lun(qr[i]);j++)
		{
			for(;ai<lun(a);ai++)
			{
				if(a[ai].fr.fr<=qr[i][j].fr.fr)break;
				uni(a[ai].fr.fr,a[ai].fr.sc,0);
			}
			s.clear();
			for(bi=0;bi<lun(b);bi++)
			{
				if(b[bi].fr.fr<=qr[i][j].fr.fr)break;
				s.in(b[bi].fr);
			}
			for(t=0;t<=qr[i][j].fr.sc;t++)
			{
				if(ed[i][t].fr.sc<=qr[i][j].fr.fr)continue;
				if(s.fd(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr))!=s.end())s.er(s.fd(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr)));
				else s.in(mkp(ed[i][t].fr.sc,ed[i][t].fr.fr));
			}
			rl.clear();
			for(it=s.begin();it!=s.end();it++)uni(it->fr,it->sc,1);
			rs[qr[i][j].sc]+=n-qr[i][j].fr.fr-er;
			reverse(all(rl));
			for(t=0;t<lun(rl);t++)
			{
				p[rl[t].fr.fr]=rl[t].fr.sc;
				sz[rl[t].sc.fr]=rl[t].sc.sc;
			}
			er-=lun(rl);
		}
	}
	return rs;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35