Submission #1188912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188912		alexdd	Collapse (JOI18_collapse)	C++20	0 / 100	15091 ms	11200 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<pair<int,int>,pair<int,int>>> edges;
void add_edge(int tle, int tri, int x, int y)
{
	assert(tle<=tri);
	assert(x<=y);
	edges.push_back({{tle,tri},{x,y}});
}
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,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);
		}
	}

	vector<int> sol((int)W.size());
	DSU dsu;
	for(int i=0;i<W.size();i++)
	{
		dsu.init();
		for(auto [t,e]:edges)
		{
			if(t.first <= W[i] && W[i] <= t.second && e.second <= P[i])
			{
				dsu.unite(e.first, e.second);
			}
		}
		int sum = dsu.get_time()/2;

		dsu.init();
		for(auto [t,e]:edges)
		{
			if(t.first <= W[i] && W[i] <= t.second && e.first > P[i])
			{
				dsu.unite(e.first, e.second);
			}
		}
		sum += dsu.get_time()/2;

		sol[i] = n - sum;
	}
	return sol;
}

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