oj.uz

Submission #244613

# Submission time Handle Problem Language Result Execution time Memory
244613 2020-07-04T12:24:46 Z MvC Collapse (JOI18_collapse) C++11
5 / 100
 15000 ms 16552 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<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 326 ms 5752 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 10 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 690 ms 5752 KB Output is correct
6 Correct 3194 ms 6152 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 10 ms 5248 KB Output is correct
9 Correct 1503 ms 6036 KB Output is correct
10 Correct 1953 ms 6032 KB Output is correct
11 Correct 3156 ms 6092 KB Output is correct
12 Correct 3068 ms 6352 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8556 KB Output is correct
2 Correct 44 ms 9144 KB Output is correct
3 Execution timed out 15015 ms 16552 KB Time limit exceeded
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 50 ms 8848 KB Output is correct
3 Correct 53 ms 9208 KB Output is correct
4 Correct 51 ms 9208 KB Output is correct
5 Correct 99 ms 9080 KB Output is correct
6 Correct 5364 ms 10180 KB Output is correct
7 Execution timed out 15014 ms 15288 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 5752 KB Output is correct
2 Correct 10 ms 5248 KB Output is correct
3 Correct 10 ms 5248 KB Output is correct
4 Correct 10 ms 5248 KB Output is correct
5 Correct 690 ms 5752 KB Output is correct
6 Correct 3194 ms 6152 KB Output is correct
7 Correct 10 ms 5376 KB Output is correct
8 Correct 10 ms 5248 KB Output is correct
9 Correct 1503 ms 6036 KB Output is correct
10 Correct 1953 ms 6032 KB Output is correct
11 Correct 3156 ms 6092 KB Output is correct
12 Correct 3068 ms 6352 KB Output is correct
13 Correct 41 ms 8556 KB Output is correct
14 Correct 44 ms 9144 KB Output is correct
15 Execution timed out 15015 ms 16552 KB Time limit exceeded
16 Halted 0 ms 0 KB -