oj.uz

Submission #244403

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

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5504 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 14 ms 5248 KB Output is correct
4 Correct 15 ms 5248 KB Output is correct
5 Correct 659 ms 5524 KB Output is correct
6 Correct 2150 ms 6008 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 11 ms 5376 KB Output is correct
9 Correct 729 ms 5624 KB Output is correct
10 Correct 1446 ms 5880 KB Output is correct
11 Correct 2232 ms 6136 KB Output is correct
12 Correct 2329 ms 6136 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 8556 KB Output is correct
2 Correct 57 ms 8556 KB Output is correct
3 Incorrect 9281 ms 13664 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 8544 KB Output is correct
3 Correct 104 ms 8556 KB Output is correct
4 Correct 163 ms 8616 KB Output is correct
5 Correct 2293 ms 8708 KB Output is correct
6 Execution timed out 15014 ms 9252 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5504 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 14 ms 5248 KB Output is correct
4 Correct 15 ms 5248 KB Output is correct
5 Correct 659 ms 5524 KB Output is correct
6 Correct 2150 ms 6008 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 11 ms 5376 KB Output is correct
9 Correct 729 ms 5624 KB Output is correct
10 Correct 1446 ms 5880 KB Output is correct
11 Correct 2232 ms 6136 KB Output is correct
12 Correct 2329 ms 6136 KB Output is correct
13 Correct 42 ms 8556 KB Output is correct
14 Correct 57 ms 8556 KB Output is correct
15 Incorrect 9281 ms 13664 KB Output isn't correct
16 Halted 0 ms 0 KB -