Submission #783063

#	Time	Username	Problem	Language	Result	Execution time	Memory
783063		kshitij_sodani	Collapse (JOI18_collapse)	C++14	100 / 100	3917 ms	33604 KiB

collapse

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;


#include "collapse.h"
int cur[100001];
int vis[100001];
int par[100001];
int ss[100001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	return find(par[no]);
}
vector<pair<int,int>> kk[3];
vector<pair<int,int>> pre[100001];
vector<pair<int,int>> pre2[100001];
vector<pair<int,int>> pre3[100001];
vector<int> pre4[100001];
int co=0;
void merge(int aa,int bb,int i){
	/*if(i==0){
		cout<<aa<<":"<<bb<<endl;
	}*/
	int x=find(aa);
	int y=find(bb);
	if(x==y){
		kk[i].pb({-1,-1});
	}
	else{
		if(ss[x]<ss[y]){
			swap(x,y);
		}
		co--;
		par[y]=x;
		ss[x]+=ss[y];
		kk[i].pb({x,y});
	}
}
void rollback(int i){
	assert(kk[i].size()>0);

	if(kk[i].back().a==-1){
		kk[i].pop_back();
	}
	else{
		pair<int,int> no=kk[i].back();
		co++;
		par[no.b]=no.b;
		ss[no.a]-=ss[no.b];
		kk[i].pop_back();
	}
}

vector<int> simulateCollapse(
	int n,
	vector<int> tt,
	vector<int> aa,
	vector<int> bb,
	vector<int> ww,
	vector<int> pp
) {
	int m=aa.size();
	int q=ww.size();
	vector<int> cc;
	map<pair<int,int>,int> ss2;
	int ind=0;
	const int ee=300;
	for(int j=0;j<m;j++){
		cur[j]=0;
	}
	for(int i=0;i<q;i++){
		pre3[(ww[i]-(ww[i]%ee))].pb({ww[i],i});
	}
	for(int i=0;i<m;i++){
		if(aa[i]>bb[i]){
			swap(aa[i],bb[i]);
		}
		if(ss2.find({aa[i],bb[i]})!=ss2.end()){
			cc.pb(ss2[{aa[i],bb[i]}]);
		}
		else{
			ss2[{aa[i],bb[i]}]=ind;
			cc.pb(ind);
			cur[ind]=0;
			ind++;
			pre2[aa[i]].pb({ss2[{aa[i],bb[i]}],bb[i]});
			pre[bb[i]].pb({ss2[{aa[i],bb[i]}],aa[i]});
		}
	}

	vector<int> ans;
	for(int i=0;i<q;i++){
		ans.pb(0);
	}
	int kk2=-1;
	for(int i=0;i<m;i+=ee){
		for(int j=kk2+1;j<i;j++){
			cur[cc[j]]^=1;
		}
		kk2=i-1;
		for(int j=0;j<n;j++){
			pre4[j].clear();
		}
		for(auto j:pre3[i]){
			pre4[pp[j.b]].pb(j.b);
		}
		for(int j=0;j<m;j++){
			vis[j]=0;
		}
		co=n;
		for(int j=0;j<3;j++){
			kk[j].clear();
		}
		for(int j=0;j<n;j++){
			par[j]=j;
			ss[j]=1;
		}
		vector<int> ll;
		for(int j=i;j<i+ee and j<m;j++){
			if(vis[cc[j]]==0){
				ll.pb(j);
			}
			vis[cc[j]]=1;
		}
		for(int j=0;j<3;j++){
			kk[j].clear();
		}
		for(int ii=n-1;ii>=0;ii--){
			for(auto j:pre2[ii]){
				if(vis[j.a]==0 and cur[j.a]==1){
					merge(ii,j.b,0);
					//cout<<ii<<"::"<<j.b<<endl;
				}
			}
		}
	
		for(int ii=0;ii<n;ii++){
			for(auto j:pre2[ii]){
				if(vis[j.a]==0 and cur[j.a]==1){
				//	cout<<11<<endl;
					rollback(0);
				}
			}
			for(auto j:pre[ii]){
				if(vis[j.a]==0 and cur[j.a]==1){
					merge(ii,j.b,1);
				}
			}
			for(auto j:pre4[ii]){
				int w=ww[j];
				for(int x=i;x<=w;x++){
					cur[cc[x]]^=1;
				}
				for(auto x:ll){
				//	cout<<x<<",,"<<cur[x]<<":"<<par[x]<<endl;
					if(cur[cc[x]]==1 and (bb[x]<=ii or aa[x]>ii)){
					//	cout<<aa[x]<<":"<<bb[x]<<":"<<x<<endl;
						merge(aa[x],bb[x],2);
					}
				}
				for(int x=i;x<=w;x++){
					cur[cc[x]]^=1;
				}
				ans[j]=co;
				while(kk[2].size()){
					rollback(2);
				}
			}
		}

	}




	return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35