Submission #220496

#	Time	Username	Problem	Language	Result	Execution time	Memory
220496		arnold518	Collapse (JOI18_collapse)	C++14	100 / 100	12599 ms	19064 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int SQ = 2000;

struct Query { int t, x, y, p; };

int N, C, Q;
Query A[MAXN+10], B[MAXN+10], V[MAXN*2+10];
vector<int> ans;

struct UF
{
	int par[MAXN+10], sz[MAXN+10];
	vector<int> S;
	void init()
	{
		int i, j;
		S.clear();
		for(i=1; i<=N; i++) par[i]=i, sz[i]=1;
	}
	int Find(int x) { return x==par[x] ? x : Find(par[x]); }
	int Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return 0;
		if(sz[x]<sz[y]) swap(x, y);
		sz[x]+=sz[y]; par[y]=x;
		S.push_back(y);
		return 1;
	}
	void restore()
	{
		int v=S.back(); S.pop_back();
		sz[par[v]]-=sz[v];
		par[v]=v;
	}
}uf;

vector<int> simulateCollapse(int _N, vector<int> _T, vector<int> _X, vector<int> _Y, vector<int> _W, vector<int> _P)
{
	int i, j, k, p, q;

	N=_N; C=_T.size(); Q=_W.size(); ans.resize(Q, N);
	for(i=0; i<C; i++) if(_X[i]>_Y[i]) swap(_X[i], _Y[i]);
	for(i=0; i<C; i++) A[i+1]={_T[i], _X[i]+1, _Y[i]+1, i+1};
	for(i=0; i<Q; i++) B[i+1]={-1, _P[i]+1, i, _W[i]+1};

	for(i=1; i<=C; i++) V[i]=A[i];
	for(i=1; i<=Q; i++) V[i+C]=B[i];

	sort(V+1, V+C+Q+1, [&](const Query &p, const Query &q)
	{
		if(p.p!=q.p) return p.p<q.p;
		else return p.t>q.t;
	});

	for(i=0; i<=(C+Q)/SQ; i++)
	{
		int l=max(1, i*SQ), r=min(C+Q, (i+1)*SQ-1);
		set<pii> S;
		vector<pii> E1, E2;
		vector<int> query;

		for(j=1; j<l; j++)
		{
			if(V[j].t==0) S.insert({V[j].x, V[j].y});
			else if(V[j].t==1) S.erase({V[j].x, V[j].y});
		}
		for(j=l; j<=r; j++)
		{
			if(V[j].t==-1)
			{
				query.push_back(j);
			}
			else
			{
				if(S.count({V[j].x, V[j].y}))
				{
					S.erase({V[j].x, V[j].y});
					E2.push_back({V[j].x, V[j].y});
				}
			}
		}
		for(auto it : S) E1.push_back(it);

		sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
		sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
		sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x<V[q].x; });

		uf.init(); j=0;
		for(auto &it : query)
		{
			for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
			set<pii> S1; vector<pii> S2;
			for(p=l; p<=it; p++)
			{
				if(V[p].t==-1) continue;
				if(V[p].y>V[it].x) continue;
				if(V[p].t==0) S1.insert({V[p].x, V[p].y});
				else S1.erase({V[p].x, V[p].y});
				S2.push_back({V[p].x, V[p].y});
			}
			sort(S2.begin(), S2.end());
			int cnt=0;
			for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
			for(auto jt : E2) if(jt.second<=V[it].x && !binary_search(S2.begin(), S2.end(), jt)) cnt+=uf.Union(jt.first, jt.second);
			ans[V[it].y]-=uf.S.size();
			while(cnt--) uf.restore();
		}

		sort(E1.begin(), E1.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
		sort(E2.begin(), E2.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
		sort(query.begin(), query.end(), [&](const int &p, const int &q) { return V[p].x>V[q].x; });

		uf.init(); j=0;
		for(auto &it : query)
		{
			for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
			set<pii> S1; vector<pii> S2;
			for(p=l; p<=it; p++)
			{
				if(V[p].t==-1) continue;
				if(V[p].x<=V[it].x) continue;
				if(V[p].t==0) S1.insert({V[p].x, V[p].y});
				else S1.erase({V[p].x, V[p].y});
				S2.push_back({V[p].x, V[p].y});
			}
			sort(S2.begin(), S2.end());
			int cnt=0;
			for(auto jt : S1) cnt+=uf.Union(jt.first, jt.second);
			for(auto jt : E2) if(jt.first>V[it].x && !binary_search(S2.begin(), S2.end(), jt)) cnt+=uf.Union(jt.first, jt.second);
			ans[V[it].y]-=uf.S.size();
			while(cnt--) uf.restore();
		}
	}

	return ans;
}

Compilation message (stderr)

collapse.cpp: In member function 'void UF::init()':
collapse.cpp:24:10: warning: unused variable 'j' [-Wunused-variable]
   int i, j;
          ^
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:100:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; j<E1.size() && E1[j].second<=V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
          ~^~~~~~~~~~
collapse.cpp:125:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; j<E1.size() && E1[j].first>V[it].x; j++) uf.Union(E1[j].first, E1[j].second);
          ~^~~~~~~~~~
collapse.cpp:48:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, p, q;
            ^
collapse.cpp:48:18: warning: unused variable 'q' [-Wunused-variable]
  int i, j, k, p, q;
                  ^

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