oj.uz

Submission #783050

# Submission time Handle Problem Language Result Execution time Memory
783050 2023-07-14T14:31:24 Z kshitij_sodani Collapse (JOI18_collapse) C++14
30 / 100
 4225 ms 33600 KB 
#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(cc[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[x]==1 and (bb[x]<=ii or aa[x]>ii)){
					//	cout<<11<<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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10112 KB Output is correct
2 Incorrect 6 ms 9812 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13308 KB Output is correct
2 Incorrect 30 ms 13384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 13300 KB Output is correct
2 Correct 29 ms 13000 KB Output is correct
3 Correct 42 ms 13128 KB Output is correct
4 Correct 54 ms 13160 KB Output is correct
5 Correct 160 ms 12972 KB Output is correct
6 Correct 159 ms 13396 KB Output is correct
7 Correct 500 ms 23900 KB Output is correct
8 Correct 1176 ms 30396 KB Output is correct
9 Correct 35 ms 17096 KB Output is correct
10 Correct 215 ms 16372 KB Output is correct
11 Correct 3191 ms 33080 KB Output is correct
12 Correct 4078 ms 33576 KB Output is correct
13 Correct 3512 ms 33000 KB Output is correct
14 Correct 4225 ms 33600 KB Output is correct
15 Correct 3321 ms 33004 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10112 KB Output is correct
2 Incorrect 6 ms 9812 KB Output isn't correct
3 Halted 0 ms 0 KB -