oj.uz

Submission #244585

# Submission time Handle Problem Language Result Execution time Memory
244585 2020-07-04T10:11:44 Z MvC Collapse (JOI18_collapse) C++11
0 / 100
 2348 ms 12784 KB 
#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=500;
const ll mod=1e9+7;
using namespace std;
int n,c,q,t,i,j,x,y,ai,bi,er,p[nmax],sz[nmax];
vector<pair<int,int> >ed[nmax],vc,a,b;
vector<pair<pair<int,int>,pair<int,int> > >rl;
vector<pair<pair<int,int>,int> >qr[nmax];
set<pair<int,int> >s;
vector<int>rs;
set<pair<int,int> >::iterator it;
map<pair<int,int>,int>v;
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(x,y));
	}
	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())continue;
		sort(all(qr[i]));
		for(j=1;j<=n;j++)
		{
			p[j]=j;
			sz[j]=1;
		}
		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));
		v.clear();
		for(j=0;j<lun(vc);j++)
		{
			v[vc[j]]^=1;
		}
		for(j=0;j<lun(ed[i]);j++)
		{
			if(v[ed[i][j]]==1)
			{
				b.pb(ed[i][j]);
				v[ed[i][j]]=0;
			}
		}
		for(j=0;j<lun(vc);j++)
		{
			if(v[vc[j]]==1)
			{
				a.pb(vc[j]);
				v[vc[j]]=0;
			}
		}
		ai=0;
		er=0;
		for(j=0;j<lun(qr[i]);j++)
		{
			for(;ai<lun(a);ai++)
			{
				if(a[ai].fr>qr[i][j].fr.fr)break;
				uni(a[ai].fr,a[ai].sc,0);
			}
			s.clear();
			for(bi=0;bi<lun(b);bi++)
			{
				if(b[bi].fr>qr[i][j].fr.fr)break;
				s.in(b[bi]);
			}
			for(t=0;t<=qr[i][j].fr.sc;t++)
			{
				if(ed[i][t].fr>qr[i][j].fr.fr)continue;
				if(s.fd(ed[i][t])!=s.end())s.er(s.fd(ed[i][t]));
				else s.in(ed[i][t]);
			}
			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,a[j].sc);
		for(j=0;j<lun(b);j++)swap(b[j].fr,b[j].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<=qr[i][j].fr.fr)break;
				uni(a[ai].fr,a[ai].sc,0);
			}
			s.clear();
			for(bi=0;bi<lun(b);bi++)
			{
				if(b[bi].fr<=qr[i][j].fr.fr)break;
				s.in(b[bi]);
			}
			for(t=0;t<=qr[i][j].fr.sc;t++)
			{
				if(ed[i][t].sc<=qr[i][j].fr.fr)continue;
				if(s.fd(mkp(ed[i][t].sc,ed[i][t].fr))!=s.end())s.er(s.fd(mkp(ed[i][t].sc,ed[i][t].fr)));
				else s.in(mkp(ed[i][t].sc,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]+=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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5504 KB Output is correct
2 Correct 11 ms 5368 KB Output is correct
3 Correct 13 ms 5248 KB Output is correct
4 Correct 16 ms 5248 KB Output is correct
5 Incorrect 70 ms 5496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8556 KB Output is correct
2 Correct 60 ms 8544 KB Output is correct
3 Incorrect 1644 ms 12784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8556 KB Output is correct
2 Correct 65 ms 8556 KB Output is correct
3 Correct 102 ms 8556 KB Output is correct
4 Correct 169 ms 8556 KB Output is correct
5 Correct 2338 ms 8816 KB Output is correct
6 Incorrect 2348 ms 9568 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5504 KB Output is correct
2 Correct 11 ms 5368 KB Output is correct
3 Correct 13 ms 5248 KB Output is correct
4 Correct 16 ms 5248 KB Output is correct
5 Incorrect 70 ms 5496 KB Output isn't correct
6 Halted 0 ms 0 KB -