Submission #65095

#	Time	Username	Problem	Language	Result	Execution time	Memory
65095		zscoder	Collapse (JOI18_collapse)	C++17	100 / 100	9743 ms	99964 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct DSU
{
	vector<int> par;
	vector<int> rank;
	vector<int> used;
	void init(int n)
	{
		par.clear(); rank.clear(); used.clear();
		for(int i=0;i<n;i++)
		{
			par.pb(i); rank.pb(1);
		}
	}
	int rt(int u)
	{
		if(par[u]==u) return u;
		else return rt(par[u]);
	}
	bool merge(int u, int v)
	{
		u=rt(u); v=rt(v);
		if(u==v) return false;
		////cerr<<"MERGE : "<<u<<' '<<v<<'\n';
		if(rank[u]<rank[v]) swap(u,v);
		used.pb(u); used.pb(v);
		rank[u]+=rank[v];
		par[v]=u;
		return true;
	}
	void reset()
	{
		for(int v:used) par[v]=v,rank[v]=1;
		used.clear();
	}
};

int ans[123456];

const int C = 800;
int n;

ii rev(ii edge)
{
	return mp(n-1-edge.fi,n-1-edge.se);
}

bool cmp(ii a, ii b)
{
	if(a.se!=b.se) return a.se<b.se;
	else return a.fi<b.fi;
}

void solve(vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query, vector<ii> fixed)
{
	int ptr_fixed = 0;
	DSU general; general.init(n); DSU specific; specific.init(n);
	int cc=0;
	for(auto x:query) 
	{
		int pos = x.fi; int lab = x.se.fi;
		while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
		{
			//cerr<<"MERGE : "<<fixed[ptr_fixed].fi<<' '<<fixed[ptr_fixed].se<<'\n';
			cc+=general.merge(fixed[ptr_fixed].fi,fixed[ptr_fixed].se); //amortized O(n)
			ptr_fixed++;
		}
		//O(sqrt(n))
		int c=0;
		for(auto it: *x.se.se)
		{
			if(it.se<=pos) 
			{
				//cerr<<"MERGE : "<<it.fi<<' '<<it.se<<' '<<general.rt(it.fi)<<' '<<general.rt(it.se)<<'\n';
				c+=specific.merge(general.rt(it.fi),general.rt(it.se));
			}
		}
		//cerr<<"CC : "<<lab<<' '<<pos<<' '<<cc+c<<'\n';
		ans[lab]+=pos+1-(cc+c);
		specific.reset();
	}
}

std::vector<int> simulateCollapse(
	int N,
	std::vector<int> T,
	std::vector<int> X,
	std::vector<int> Y,
	std::vector<int> W,
	std::vector<int> P
) 
{
	vi answer; answer.resize(int(W.size())); n=N;
	set<ii> curset; //set of current paths
	vector<pair<int,ii> > queries;
	for(int i=0;i<T.size();i++)
	{
		if(X[i]>Y[i]) swap(X[i],Y[i]);
	}
	for(int i=0;i<W.size();i++)
	{
		queries.pb(mp(W[i],mp(P[i],i)));
	}
	sort(queries.begin(),queries.end());
	int curptr = 0;
	for(int l=0;l<T.size();l+=C) //O(sqrt(N))
	{
		int r = min(l+C-1,int(T.size())-1);
		//solve all queries where l<=W<=r
		set<ii> fixed = curset; //stores the edges that wont be changed this block
		set<ii> change; //stores the set of edges that will be changed this block
		for(int i=l;i<=r;i++) change.insert(mp(X[i],Y[i]));
		set<ii> dynamic; //stores the current progress of the edges changed in this block
		for(auto edge:change)
		{
			if(fixed.find(edge)!=fixed.end())
			{
				fixed.erase(edge); dynamic.insert(edge);
			}
		}
		vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query1,query2;
		for(int i=l;i<=r;i++) //O(sqrt(N))
		{
			if(!T[i])
			{
				curset.insert(mp(X[i],Y[i])); dynamic.insert(mp(X[i],Y[i]));
			}
			else
			{
				curset.erase(mp(X[i],Y[i])); dynamic.erase(mp(X[i],Y[i]));
			}
			shared_ptr<vector<ii> > p1(new vector<ii>), p2(new vector<ii>); //shared_ptr new trick acquired
			for(auto edge:dynamic) //O(sqrt(N))
			{
				p1->pb(edge);
				p2->pb(mp(rev(edge).se,rev(edge).fi));
			}
			while(curptr<queries.size()&&queries[curptr].fi<=i)
			{
				query1.pb(mp(queries[curptr].se.fi,mp(queries[curptr].se.se, p1)));
				query2.pb(mp(n-2-queries[curptr].se.fi,mp(queries[curptr].se.se, p2)));
				curptr++;
			}
		}
		sort(query1.begin(),query1.end());
		sort(query2.begin(),query2.end()); //hope shared pointer doesn't get sorted
		vector<ii> fixed2;
		for(auto x:fixed) fixed2.pb(x);
		sort(fixed2.begin(),fixed2.end(),cmp);
		solve(query1, fixed2);
		for(auto &x:fixed2) {x.fi=n-1-x.fi; x.se=n-1-x.se; swap(x.fi,x.se);}
		sort(fixed2.begin(),fixed2.end(),cmp);
		solve(query2, fixed2);
	}
	for(int i=0;i<answer.size();i++) answer[i]=ans[i];
	return answer;
}

Compilation message (stderr)

collapse.cpp: In function 'void solve(std::vector<std::pair<int, std::pair<int, std::shared_ptr<std::vector<std::pair<int, int> > > > > >, std::vector<std::pair<int, int> >)':
collapse.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
         ~~~~~~~~~^~~~~~~~~~~~~
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:114:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++)
              ~^~~~~~~~~
collapse.cpp:118:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++)
              ~^~~~~~~~~
collapse.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=0;l<T.size();l+=C) //O(sqrt(N))
              ~^~~~~~~~~
collapse.cpp:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curptr<queries.size()&&queries[curptr].fi<=i)
          ~~~~~~^~~~~~~~~~~~~~~
collapse.cpp:173:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<answer.size();i++) answer[i]=ans[i];
              ~^~~~~~~~~~~~~~

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