Submission #145637

#	Time	Username	Problem	Language	Result	Execution time	Memory
145637		TadijaSebez	Collapse (JOI18_collapse)	C++11	100 / 100	7133 ms	23668 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int S=317;
struct DSU
{
	int p[N],z[N],n,cmp,S[N],c;
	void init(int _n){ n=_n;for(int i=1;i<=n;i++) p[i]=i,z[i]=1;cmp=n;c=0;}
	DSU(){}
	int Find(int x){ return p[x]==x?x:Find(p[x]);}
	void Union(int x, int y, bool bck)
	{
		x=Find(x);y=Find(y);
		if(x==y){ if(bck) S[++c]=0;return;}
		cmp--;
		if(z[x]>z[y]) swap(x,y);
		p[x]=y;
		z[y]+=z[x];
		S[++c]=x;
	}
	void Undo()
	{
		if(!S[c]) c--;
		else
		{
			cmp++;
			int x=S[c--];
            z[p[x]]-=z[x];
            p[x]=x;
		}
	}
} DS;
int n,m,q;
int t[N],x[N],y[N],rng[N],w[N],p[N],ans[N];
map<pair<int,int>,int> last;
vector<int> Qs[N];
vector<int> Solve()
{
	for(int i=1;i<=m;i++)
	{
		if(t[i]==0) rng[i]=m,last[{x[i],y[i]}]=i;
		else rng[last[{x[i],y[i]}]]=i-1;
	}
	for(int l=1;l<=m;l+=S)
	{
		int r=min(m,l+S-1);
		vector<int> add,now;
		for(int i=1;i<=r;i++)
		{
			if(t[i]==1 || rng[i]<l) continue;
			if(rng[i]<=r || i>=l) add.pb(i);
			else now.pb(i);
		}
		vector<int> qs;
		for(int i=l;i<=r;i++) for(int Q:Qs[i]) qs.pb(Q);
		sort(now.begin(),now.end(),[&](int i, int j){ return y[i]<y[j];});
		sort(qs.begin(),qs.end(),[&](int i, int j){ return p[i]<p[j];});
        int e_ptr=0,q_ptr=0;
        DS.init(n);
        for(int i=1;i<=n;i++)
		{
			while(e_ptr<now.size() && y[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
			while(q_ptr<qs.size() && p[qs[q_ptr]]==i)
			{
				int qid=qs[q_ptr];
				int cnt=0;
				for(int e:add) if(w[qid]>=e && w[qid]<=rng[e] && y[e]<=p[qid]) DS.Union(x[e],y[e],1),cnt++;
				ans[qid]+=DS.cmp-(n-i);
				while(cnt--) DS.Undo();
				q_ptr++;
			}
		}
		sort(now.begin(),now.end(),[&](int i, int j){ return x[i]>x[j];});
		reverse(qs.begin(),qs.end());
		e_ptr=q_ptr=0;
		DS.init(n);
		for(int i=n;i>=1;i--)
		{
			while(e_ptr<now.size() && x[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
			while(q_ptr<qs.size() && p[qs[q_ptr]]==i-1)
			{
				int qid=qs[q_ptr];
				int cnt=0;
				for(int e:add) if(w[qid]>=e && w[qid]<=rng[e] && x[e]>p[qid]) DS.Union(x[e],y[e],1),cnt++;
				ans[qid]+=DS.cmp-p[qid];
				while(cnt--) DS.Undo();
				q_ptr++;
			}
		}
	}
	vector<int> ret;
	for(int i=1;i<=q;i++) ret.pb(ans[i]);
	return ret;
}
vector<int> simulateCollapse(int _n, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P)
{
	n=_n;m=X.size();q=W.size();
	for(int i=1;i<=m;i++) t[i]=T[i-1],x[i]=X[i-1]+1,y[i]=Y[i-1]+1;
	for(int i=1;i<=q;i++) w[i]=W[i-1]+1,p[i]=P[i-1]+1,Qs[w[i]].pb(i);
	for(int i=1;i<=m;i++) if(x[i]>y[i]) swap(x[i],y[i]);
	return Solve();
}

Compilation message (stderr)

collapse.cpp: In function 'std::vector<int> Solve()':
collapse.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(e_ptr<now.size() && y[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
          ~~~~~^~~~~~~~~~~
collapse.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(q_ptr<qs.size() && p[qs[q_ptr]]==i)
          ~~~~~^~~~~~~~~~
collapse.cpp:81:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(e_ptr<now.size() && x[now[e_ptr]]==i) DS.Union(x[now[e_ptr]],y[now[e_ptr]],0),e_ptr++;
          ~~~~~^~~~~~~~~~~
collapse.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(q_ptr<qs.size() && p[qs[q_ptr]]==i-1)
          ~~~~~^~~~~~~~~~

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