Submission #1141746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141746		Noproblem29	Collapse (JOI18_collapse)	C++20	5 / 100	220 ms	100276 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
int n,m,q;
int p[N];
int pos[N*3];
int cus[N*3];
vector<int>ans;
int dsu(int x){
	while(p[x]>=0)x=p[x];
	return x;
}
int sz;
stack<tuple<int,int,bool>>st;
void merge(int x,int y){
    x=dsu(x);
    y=dsu(y);
    if(x==y)return;
    if(p[x]<p[y])swap(x,y);
    st.push({x,p[x],(p[x]==p[y])});
    if(p[x]==p[y]){
        p[y]--;
    }
    sz--;
    p[x]=y;
}
void rollback(int t){
    while(st.size()>t){
        auto [x,pxe,ch]=st.top();
        st.pop();
        if(ch){
            p[p[x]]++;
        }
        p[x]=pxe;
		sz++;
    }
}
void solve1(vector<int>&t,vector<int>&x,vector<int>&y,vector<int>&w,vector<int>&ps){
	map<pair<int,int>,int>last;
	for(int i=0;i<m;i++){
		if(x[i]>y[i])swap(x[i],y[i]);
		if(last.count({x[i],y[i]})){
			pos[i]=last[{x[i],y[i]}];
			pos[pos[i]]=i;
			last.erase({x[i],y[i]});
		}
		else{
			last[{x[i],y[i]}]=i;
		}
	}
	for(auto i:last){
		pos[i.second]=m;
	}
	for(int i=0;i<q;i++){
		for(int j=0;j<n;j++){
			p[j]=-1;
		}
		sz=n;
		for(int j=0;j<=w[i];j++){
			if(x[j]<=ps[i]&&ps[i]+1<=y[j]){
				continue;
			}
			if(pos[j]>w[i]){
				merge(x[j],y[j]);
			}
		}
		ans[i]=sz;
	}
}
void sl2(int l,int r,vector<int>&x,vector<int>&y,int lim){
	if(l>r)return;
	if(l==r){
		cus[l]=sz;
		return;
	}
	int mid=(l+r)>>1ll;
	int cur=st.size();
	for(int i=mid+1;i<=r;i++){
		if(x[i]<=lim&&lim+1<=y[i])continue;
		if(pos[i]<l){
			merge(x[i],y[i]);
		}
	}
	sl2(l,mid,x,y,lim);
	rollback(cur);
	for(int i=l;i<=mid;i++){
		if(x[i]<=lim&&lim+1<=y[i])continue;
		if(pos[i]>r){
			merge(x[i],y[i]);
		}
	}
	sl2(mid+1,r,x,y,lim);
	rollback(cur);
}
void solve2(vector<int>&t,vector<int>&x,vector<int>&y,vector<int>&w,vector<int>&ps){
	map<pair<int,int>,int>last;
	for(int i=0;i<m;i++){
		if(x[i]>y[i])swap(x[i],y[i]);
		if(last.count({x[i],y[i]})){
			pos[i]=last[{x[i],y[i]}];
			pos[pos[i]]=i;
			last.erase({x[i],y[i]});
		}
		else{
			last[{x[i],y[i]}]=i;
		}
	}
	for(auto i:last){
		pos[i.second]=m;
		pos[m]=i.second;
		x.push_back(i.first.first);
		y.push_back(i.first.second);
		m++;
	}
	x.push_back(0);
	y.push_back(0);
	m++;
	for(int i=0;i<n;i++){
		p[i]=-1;
	}
	sz=n;
	sl2(0,m-1,x,y,ps.front());
	for(int i=0;i<q;i++){
		ans[i]=cus[w[i]+1];
	}
}
vector<int> simulateCollapse(int _n,vector<int> t,vector<int> x,vector<int> y,vector<int> w,vector<int> ps) {
	n=_n;
	m=x.size();
	q=w.size();
	ans.resize(q,-1);
	if(n<=5000&&m<=5000&&q<=5000){
		solve1(t,x,y,w,ps);
		return ans;
	}
	if(is_sorted(ps.begin(),ps.end())&&ps.front()==ps.back()){
		solve2(t,x,y,w,ps);
		return ans;
	}
	return ans;
}

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