Submission #1141650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141650		Noproblem29	Collapse (JOI18_collapse)	C++20	5 / 100	163 ms	2632 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];
vector<int>ans;
int dsu(int x){
	while(p[x]>=0)x=p[x];
	return x;
}
int sz;
void merge(int x,int y){
	x=dsu(x);
	y=dsu(y);
	if(x==y)return;
	if(p[x]<p[y])swap(x,y);
	if(p[x]==p[y])p[y]--;
	p[x]=y;
	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 solve2(){

}
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,0);
	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();
		return ans;
	}
	return ans;
}

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