Submission #1188962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188962		alexdd	Collapse (JOI18_collapse)	C++20	0 / 100	15091 ms	40408 KiB

collapse

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

struct DSU
{
	int father[100005],siz[100005];
	vector<pair<pair<int,int>,int>> history;
	void init()
	{
		history.clear();
		for(int i=0;i<n;i++)
			father[i]=i, siz[i]=1;
	}
	int gas(int x)
	{
		if(father[x]!=x)
			return gas(father[x]);
		return x;
	}
	void unite(int x, int y)
	{
		x = gas(x);
		y = gas(y);
		if(x==y)
			return;
		history.push_back({{y,father[y]},0});
		history.push_back({{x,siz[x]},1});
		father[y] = x;
		siz[x] += siz[y];
	}
	int get_time()
	{
		return history.size();
	}
	void rollback(int t)
	{
		while((int)history.size() > t)
		{
			if(history.back().second == 0)
				father[history.back().first.first] = history.back().first.second;
			else
				siz[history.back().first.first] = history.back().first.second;
			history.pop_back();
		}
	}
};

vector<pair<int,int>> begin_on_t[100005],end_on_t[100005];
vector<pair<int,pair<int,int>>> begin_on_poz[100005],end_on_poz[100005];
void add_edge(int tle, int tri, int x, int y)
{
	assert(tle<=tri);
	assert(x<=y);

	begin_on_t[tle].push_back({x,y});
	end_on_t[tri].push_back({x,y});
	begin_on_poz[x].push_back({y,{tle,tri}});
	end_on_poz[y].push_back({x,{tle,tri}});
}

vector<pair<pair<int,int>,int>> qrys;
const int BUC = 350;
bool cmp_mo(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)///--------------------------------------------------------------
{
	if(x.first.first/BUC != y.first.first/BUC)
		return x.first.first/BUC < y.first.first/BUC;
	if((x.first.first/BUC)%2==0)
		return x.first.second < y.first.second;
	else
		return x.first.second > y.first.second;
}

vector<pair<int,int>> on_node[400005];
int who[100005];
void upd(int nod, int st, int dr, int le, int ri, int x, int y)
{
	if(le>ri)
		return;
	if(le==st && dr==ri)
	{
		on_node[nod].push_back({x,y});
		return;
	}
	int mij=(st+dr)/2;
	upd(nod*2,st,mij,le,min(mij,ri),x,y);
	upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,x,y);
}

vector<int> sol;
DSU dsu;
void dfs_dynamic(int nod, int st, int dr)
{
	int old_t = dsu.get_time();
	for(auto [x,y]:on_node[nod])
		dsu.unite(x,y);
	if(st==dr)
	{
		sol[who[st]] = n - dsu.get_time()/2;
	}
	else
	{
		int mij=(st+dr)/2;
		dfs_dynamic(nod*2,st,mij);
		dfs_dynamic(nod*2+1,mij+1,dr);
	}
	dsu.rollback(old_t);
}

void add_dynamic_edge(int tle, int tri, int x, int y)
{
	if(tle>tri)
		return;
	upd(1,1,qrys.size(),tle,tri,x,y);
}
map<pair<int,int>,int> dynamic_time;
void baga_dynamic(int t, int x, int y)
{
	if(x>y)
		swap(x,y);
	dynamic_time[{x,y}] = t;
}
void scoate_dynamic(int t, int x, int y)
{
	if(x>y)
		swap(x,y);
	if(dynamic_time[{x,y}])
	{
		add_dynamic_edge(dynamic_time[{x,y}],t-1,x,y);
		dynamic_time[{x,y}] = 0;
	}
}

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)
{
	n=N;
	map<pair<int,int>,int> construction_day;
	for(int i=0;i<T.size();i++)
	{
		if(X[i] > Y[i])
			swap(X[i],Y[i]);
		if(T[i]==0)
		{
			construction_day[{X[i],Y[i]}] = i;
		}
		else
		{
			add_edge(construction_day[{X[i],Y[i]}],i-1,X[i],Y[i]);
			construction_day[{X[i],Y[i]}] = -1;
		}
	}
	for(auto it:construction_day)
	{
		if(it.second != -1)
		{
			add_edge(it.second, (int)T.size() + 2, it.first.first, it.first.second);
		}
	}

	for(int i=0;i<W.size();i++)
	{
		qrys.push_back({{W[i],P[i]},i});
	}
	sort(qrys.begin(),qrys.end(),cmp_mo);
	int myt = -1, myp = qrys[0].first.second;
	for(int i=1;i<=qrys.size();i++)
	{
		int w = qrys[i-1].first.first, p = qrys[i-1].first.second, id = qrys[i-1].second;
		who[i] = id;

		while(myt < w)
		{
			if(myt!=-1)
				for(auto [x,y]:end_on_t[myt])
					scoate_dynamic(i,x,y);
			myt++;
			for(auto [x,y]:begin_on_t[myt])
				if(y <= p || x > p)
					baga_dynamic(i,x,y);
		}
		while(myt > w)
		{
			for(auto [x,y]:begin_on_t[myt])
				scoate_dynamic(i,x,y);
			myt--;
			for(auto [x,y]:end_on_t[myt])
				if(y <= p || x > p)
					baga_dynamic(i,x,y);
		}

		while(myp < p)
		{
			myp++;
			for(auto [other_poz,t]:end_on_poz[myp])
				if(t.first <= w && w <= t.second)
					baga_dynamic(i,other_poz,myp);
			for(auto [other_poz,t]:begin_on_poz[myp])
				scoate_dynamic(i,myp,other_poz);
		}
		while(myp > p)
		{
			for(auto [other_poz,t]:end_on_poz[myp])
					scoate_dynamic(i,other_poz,myp);
			for(auto [other_poz,t]:begin_on_poz[myp])
				if(t.first <= w && w <= t.second)
					baga_dynamic(i,myp,other_poz);
			myp--;
		}
	}
	for(auto it:dynamic_time)
		if(it.second != 0)
			scoate_dynamic((int)qrys.size() + 2, it.first.first, it.first.second);

	sol.resize(W.size());
	dsu.init();
	dfs_dynamic(1,1,qrys.size());
	/*vector<int> sol((int)W.size());
	for(int dyn_t=1;dyn_t<=qrys.size();dyn_t++)
	{
		int id = who[dyn_t];
		DSU dsu;
		dsu.init();
		for(auto [t,e]:dynamic_edges)
		{
			if(t.first <= dyn_t && dyn_t <= t.second)
			{
				dsu.unite(e.first, e.second);
			}
		}
		sol[id] = n - dsu.get_time()/2;
	}*/
	return sol;
}

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