oj.uz

Submission #244394

# Submission time Handle Problem Language Result Execution time Memory
244394 2020-07-03T19:37:23 Z MvC Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 16596 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=1;
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<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;
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(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())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].fr]^=1;
		}
		for(j=0;j<lun(ed[i]);j++)
		{
			if(v[ed[i][j].fr])
			{
				b.pb(ed[i][j]);
				v[ed[i][j].fr]=0;
			}
		}
		for(j=0;j<lun(vc);j++)if(v[vc[j].fr])a.pb(vc[j]),v[vc[j].fr]=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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 6056 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 10 ms 5376 KB Output is correct
4 Correct 11 ms 5248 KB Output is correct
5 Correct 1159 ms 6048 KB Output is correct
6 Correct 3216 ms 6668 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 10 ms 5376 KB Output is correct
9 Correct 1577 ms 6264 KB Output is correct
10 Correct 2035 ms 6400 KB Output is correct
11 Correct 3151 ms 6456 KB Output is correct
12 Correct 3094 ms 6656 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 8812 KB Output is correct
2 Correct 41 ms 9400 KB Output is correct
3 Execution timed out 15069 ms 16596 KB Time limit exceeded
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 50 ms 8848 KB Output is correct
3 Correct 64 ms 9212 KB Output is correct
4 Correct 53 ms 9372 KB Output is correct
5 Correct 101 ms 9116 KB Output is correct
6 Correct 5391 ms 10992 KB Output is correct
7 Execution timed out 15064 ms 16224 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 6056 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 10 ms 5376 KB Output is correct
4 Correct 11 ms 5248 KB Output is correct
5 Correct 1159 ms 6048 KB Output is correct
6 Correct 3216 ms 6668 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 10 ms 5376 KB Output is correct
9 Correct 1577 ms 6264 KB Output is correct
10 Correct 2035 ms 6400 KB Output is correct
11 Correct 3151 ms 6456 KB Output is correct
12 Correct 3094 ms 6656 KB Output is correct
13 Correct 40 ms 8812 KB Output is correct
14 Correct 41 ms 9400 KB Output is correct
15 Execution timed out 15069 ms 16596 KB Time limit exceeded
16 Halted 0 ms 0 KB -