oj.uz

Submission #244612

# Submission time Handle Problem Language Result Execution time Memory
244612 2020-07-04T12:21:44 Z MvC Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 13392 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>,int> >qr[nmax];
set<pair<int,int> >s;
vector<int>rs,rl;
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(y);
	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,n);
	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=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]-=er;
			reverse(all(rl));
			for(t=0;t<lun(rl);t++)
			{
				y=rl[t];
				sz[p[y]]-=sz[y];
				p[y]=y;
			}
			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=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]-=er;
			reverse(all(rl));
			for(t=0;t<lun(rl);t++)
			{
				y=rl[t];
				sz[p[y]]-=sz[y];
				p[y]=y;
			}
			er-=lun(rl);
		}
	}
	return rs;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5496 KB Output is correct
2 Correct 11 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 638 ms 5496 KB Output is correct
6 Correct 2159 ms 6016 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 731 ms 5752 KB Output is correct
10 Correct 1460 ms 5880 KB Output is correct
11 Correct 2335 ms 6284 KB Output is correct
12 Correct 2432 ms 6336 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 60 ms 8556 KB Output is correct
3 Incorrect 9335 ms 13392 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8564 KB Output is correct
2 Correct 69 ms 8556 KB Output is correct
3 Correct 104 ms 8556 KB Output is correct
4 Correct 174 ms 8556 KB Output is correct
5 Correct 2360 ms 8760 KB Output is correct
6 Execution timed out 15095 ms 9272 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 5496 KB Output is correct
2 Correct 11 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 638 ms 5496 KB Output is correct
6 Correct 2159 ms 6016 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 12 ms 5376 KB Output is correct
9 Correct 731 ms 5752 KB Output is correct
10 Correct 1460 ms 5880 KB Output is correct
11 Correct 2335 ms 6284 KB Output is correct
12 Correct 2432 ms 6336 KB Output is correct
13 Correct 43 ms 8556 KB Output is correct
14 Correct 60 ms 8556 KB Output is correct
15 Incorrect 9335 ms 13392 KB Output isn't correct
16 Halted 0 ms 0 KB -