Submission #129341

#	Time	Username	Problem	Language	Result	Execution time	Memory
129341		qkxwsm	Collapse (JOI18_collapse)	C++14	5 / 100	15083 ms	28596 KiB

collapse

#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969
#define MAXN 100013
#define MAGIC 521

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, Q;
vi ans;
unordered_set<int> edges[MAXN], ins[MAXN], beg[MAXN];
vector<array<int, 4> > events;
vector<array<int, 4> > block;
bitset<MAXN> seen;
vi ord;

bool cmp(int a, int b)
{
	return block[a][2] < block[b][2];
}
struct dsu
{
	int dsu[MAXN], siz[MAXN];
	void init()
	{
		FOR(i, 0, N)
		{
			dsu[i] = i;
			siz[i] = 1;
		}
	}
	int get(int u)
	{
		return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
	}
	bool merge(int u, int v)
	{
		u = get(u); v = get(v);
		if (u == v) return false;
		if (siz[u] > siz[v]) swap(u, v);
		siz[v] += siz[u];
		dsu[u] = v;
		return true;
	}
};

dsu D[2];

void proc()
{
	seen.reset();
	vi nodes;
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) continue;
		if (!seen[block[i][2]])
		{
			nodes.PB(block[i][2]);
			seen[block[i][2]] = true;
		}
		if (!seen[block[i][3]])
		{
			nodes.PB(block[i][3]);
			seen[block[i][3]] = true;
		}
	}
	D[0].init(); D[1].init();
	FOR(i, 0, N)
	{
		beg[i] = edges[i];
	}
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 1)
		{
			int u = block[i][2], v = block[i][3];
			if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
		}
	}
	for (int u : nodes)
	{
		for (int v : edges[u])
		{
			beg[v].erase(v);
		}
	}
	int cp = -1, cc = 0;
	ord.clear();
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) ord.PB(i);
	}
	sort(ALL(ord), cmp);
	for (int idx : ord)
	{
		int t = block[idx][0], x = block[idx][2], qid = block[idx][3];
		while(cp < x)
		{
			cp++; cc++;
			for (int w : edges[cp]) if (D[0].merge(cp, w)) cc--;
		}
		int res = cc;
		for (int u : nodes)
		{
			ins[u] = beg[u];
		}
		FOR(j, 0, SZ(block))
		{
			if (block[j][0] > t) break;
			if (block[j][1] == 2) continue;
			int u = block[j][2], v = block[j][3];
			if (v > x) continue;
			if (block[j][1] == 1)
			{
				if (ins[v].find(u) != ins[v].end()) ins[v].erase(u);
			}
			else
			{
				ins[v].insert(u);
			}
		}
		for (int u : nodes)
		{
			if (u > x) continue;
			int ve = D[0].get(u);
			for (int w : ins[u])
			{
				if (D[1].merge(ve, D[0].get(w))) res--;
			}
			ins[u].clear();
		}
		for (int u : nodes)
		{
			int v = D[0].get(u);
			D[1].dsu[v] = v; D[1].siz[v] = 1;
		}
		// cerr << res << endl;
		ans[qid] += res;
	}
	for (int u : nodes)
	{
		for (int x : beg[u])
		{
			edges[u].insert(x);
		}
	}
	FOR(i, 0, SZ(block))
	{
		if (block[i][1] == 2) continue;
		int u = block[i][2], v = block[i][3];
		if (block[i][1] == 1)
		{
			if (edges[v].find(u) != edges[v].end()) edges[v].erase(u);
		}
		else
		{
			edges[v].insert(u);
		}
	}
	//build the set of edges now!
}
void solve()
{
	//find # of cc's with value LESS THAN whatever
	//sort all the queries in the block.
	//after processing the block, the sets should store all active edges.
	// FOR(i, 0, SZ(events))
	// {
	// 	assert(events[i][1] == 2 || events[i][2] < events[i][3]);
	// }
	for (int i = 0; i < SZ(events); i += MAGIC)
	{
		for (int j = i; j < SZ(events) && j < i + MAGIC; j++)
		{
			block.PB(events[j]);
		}
		proc();
		block.clear();
	}
}
vi simulateCollapse(int n, vi t, vi x, vi y, vi w, vi p)
{
	N = n; Q = SZ(w);
	ans.resize(Q);
	FOR(i, 0, SZ(t))
	{
		if (x[i] > y[i]) swap(x[i], y[i]);
		events.PB({i, t[i], x[i], y[i]});
	}
	FOR(i, 0, Q)
	{
		events.PB({w[i], 2, p[i], i});
	}
	sort(ALL(events));
	FOR(i, 0, SZ(events))
	{
		events[i][0] = i;
	}
	// cerr << "SOLVE\n";
	solve();
	FOR(i, 0, N)
	{
		edges[i].clear();
		ins[i].clear();
	}
	for (auto &e : events)
	{
		if (e[1] == 2)
		{
			e[2] = N - 2 - e[2];
		}
		else
		{
			e[2] = N - 1 - e[2];
			e[3] = N - 1 - e[3];
			swap(e[2], e[3]);
		}
	}
	// cerr << "SOLVE\n";
	solve();
	return ans;
	//event: disconnect u -> v, connect u -> v, ask qid x pos y: so you store time, typ, who it happens to
	return ans;
}

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