oj.uz

Submission #244356

# Submission time Handle Problem Language Result Execution time Memory
244356 2020-07-03T17:30:45 Z MvC Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 16476 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=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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5504 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 13 ms 5248 KB Output is correct
4 Correct 16 ms 5248 KB Output is correct
5 Correct 643 ms 5624 KB Output is correct
6 Correct 2088 ms 5752 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 728 ms 5624 KB Output is correct
10 Correct 1445 ms 5684 KB Output is correct
11 Correct 2220 ms 6016 KB Output is correct
12 Correct 2320 ms 5920 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8556 KB Output is correct
2 Correct 57 ms 8684 KB Output is correct
3 Incorrect 9317 ms 16476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8564 KB Output is correct
2 Correct 64 ms 8556 KB Output is correct
3 Correct 101 ms 8684 KB Output is correct
4 Correct 163 ms 8684 KB Output is correct
5 Correct 2202 ms 8688 KB Output is correct
6 Execution timed out 15089 ms 9392 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5504 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 13 ms 5248 KB Output is correct
4 Correct 16 ms 5248 KB Output is correct
5 Correct 643 ms 5624 KB Output is correct
6 Correct 2088 ms 5752 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 728 ms 5624 KB Output is correct
10 Correct 1445 ms 5684 KB Output is correct
11 Correct 2220 ms 6016 KB Output is correct
12 Correct 2320 ms 5920 KB Output is correct
13 Correct 43 ms 8556 KB Output is correct
14 Correct 57 ms 8684 KB Output is correct
15 Incorrect 9317 ms 16476 KB Output isn't correct
16 Halted 0 ms 0 KB -