oj.uz

Submission #547800

# Submission time Handle Problem Language Result Execution time Memory
547800 2022-04-11T19:15:14 Z blue Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 5304 KB 
#include "collapse.h"
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int bs = 1;





struct dss
{
	int Z;
	vi parent;
	vi subtree;

	dss()
	{
		;
	}

	dss(int Z_)
	{
		Z = Z_;
		parent = subtree = vi(Z);
		for(int i = 0; i < Z; i++)
		{
			parent[i] = i;
			subtree[i] = 1;
		}
	}

	int root(int u)
	{
		if(parent[u] == u) return u;
		else return (parent[u] = root(parent[u]));
	}

	bool join(int u, int v)
	{
		u = root(u);
		v = root(v);
		if(u == v) return 0;
		if(subtree[u] < subtree[v]) swap(u, v);
		parent[v] = u;
		subtree[u] += subtree[v];
		return 1;
	}

	bool connected(int u, int v)
	{
		return root(u) == root(v);
	}
};






vi simulateCollapse(int N, vi T, vi X, vi Y, vi W, vi P)
{	
	int C = sz(X);
	int Q = sz(W);

	for(int i = 0; i < C; i++)
	{
		if(X[i] > Y[i])
			swap(X[i], Y[i]);
	}

	vi queries[N];
	for(int q = 0; q < Q; q++)
		queries[P[q]].push_back(q);

	vi res(Q);




	for(int bl = 0; bl*bs < C; bl++)
	{
		int l = bl*bs, r = min((bl+1)*bs - 1, C-1);

		// cerr << "l r = " << l << ' ' << r << '\n';

		set<pii> critical;
		for(int i = l; i <= r; i++)
		{
			critical.insert({X[i], Y[i]});
		}

		set<pii> edgeset;

		for(int i = 0; i < l; i++)
		{
			if(critical.find({X[i], Y[i]}) != critical.end())
				continue;

			if(T[i] == 0)
				edgeset.insert({X[i], Y[i]});
			else
				edgeset.erase({X[i], Y[i]});
		}

		vi fwdedge[N], backedge[N];
		for(auto e : edgeset)
		{
			fwdedge[e.first].push_back(e.second);
			backedge[e.second].push_back(e.first);
		}





























		dss dsu1(N);

		int comps = 0;

		vi checkedge[N];
		vi vis(N, 0);


		for(int i = 0; i <= N-2; i++)
		{
			comps++;

			for(int j : backedge[i])
			{
				comps -= dsu1.join(i, j);
			}

			for(int q : queries[i])
			{
				int t = W[q];

				if(!(l <= t && t <= r)) continue;

				set<pii> currcritical;
				vi vertlist;

				for(int ei = l; ei <= r; ei++)
				{
					if(Y[ei] >= P[q] + 1) continue;
					if(ei > W[q]) continue;

					if(T[ei] == 0)
						currcritical.insert({X[ei], Y[ei]});
					else
						currcritical.erase({X[ei], Y[ei]});
				}

				for(auto k : currcritical)
				{
					int rx = dsu1.root(k.first);
					int ry = dsu1.root(k.second);

					checkedge[rx].push_back(ry);
					checkedge[ry].push_back(rx);

					vertlist.push_back(rx);
					vertlist.push_back(ry);
				}

				int thiscomps = comps;

				for(int z : vertlist)
				{
					if(vis[z]) continue;

					queue<int> tbv;
					tbv.push(z);
					vis[z] = 1;

					while(!tbv.empty())
					{
						int u = tbv.front();
						tbv.pop();

						for(int v : checkedge[u])
						{
							if(vis[v]) continue;
							vis[v] = 1;
							thiscomps--;
							tbv.push(v);
						}
					}
				}

				for(int v : vertlist)
				{
					vis[v] = 0;
					checkedge[v].clear();
				}

				res[q] += thiscomps;
				// cerr << "thiscomps = " << thiscomps << '\n';
			}
		}






















		dss dsu2(N);

		comps = 0;

		for(int i = 0; i < N; i++)
			checkedge[i].clear();

		vis = vi(N, 0);


		for(int i = N-1; i >= 1; i--)
		{
			comps++;

			for(int j : fwdedge[i])
			{
				comps -= dsu2.join(i, j);
			}

			for(int q : queries[i-1])
			{
				int t = W[q];
				if(!(l <= t && t <= r)) continue;

				set<pii> currcritical;
				vi vertlist;

				for(int ei = l; ei <= r; ei++)
				{
					if(X[ei] <= P[q]) continue;
					if(ei > W[q]) continue;

					if(T[ei] == 0)
						currcritical.insert({X[ei], Y[ei]});
					else
						currcritical.erase({X[ei], Y[ei]});
				}

				for(auto k : currcritical)
				{
					int rx = dsu2.root(k.first);
					int ry = dsu2.root(k.second);

					checkedge[rx].push_back(ry);
					checkedge[ry].push_back(rx);

					vertlist.push_back(rx);
					vertlist.push_back(ry);
				}

				int thiscomps = comps;

				for(int z : vertlist)
				{
					if(vis[z]) continue;

					queue<int> tbv;
					tbv.push(z);
					vis[z] = 1;

					while(!tbv.empty())
					{
						int u = tbv.front();
						tbv.pop();

						for(int v : checkedge[u])
						{
							if(vis[v]) continue;
							vis[v] = 1;
							thiscomps--;
							tbv.push(v);
						}
					}
				}

				for(int v : vertlist)
				{
					vis[v] = 0;
					checkedge[v].clear();
				}

				res[q] += thiscomps;
				// cerr << "thiscomps = " << thiscomps << '\n';
			}
		}
	}




	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 528 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 456 KB Output is correct
5 Correct 1303 ms 556 KB Output is correct
6 Correct 2858 ms 900 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 1951 ms 1204 KB Output is correct
10 Correct 2791 ms 1384 KB Output is correct
11 Correct 5038 ms 1856 KB Output is correct
12 Correct 4747 ms 1792 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2764 KB Output is correct
2 Correct 50 ms 2772 KB Output is correct
3 Execution timed out 15079 ms 5072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2744 KB Output is correct
2 Correct 44 ms 2704 KB Output is correct
3 Correct 63 ms 2844 KB Output is correct
4 Correct 99 ms 2752 KB Output is correct
5 Correct 709 ms 2768 KB Output is correct
6 Correct 9099 ms 3408 KB Output is correct
7 Execution timed out 15057 ms 5304 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 528 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 456 KB Output is correct
5 Correct 1303 ms 556 KB Output is correct
6 Correct 2858 ms 900 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 6 ms 1108 KB Output is correct
9 Correct 1951 ms 1204 KB Output is correct
10 Correct 2791 ms 1384 KB Output is correct
11 Correct 5038 ms 1856 KB Output is correct
12 Correct 4747 ms 1792 KB Output is correct
13 Correct 26 ms 2764 KB Output is correct
14 Correct 50 ms 2772 KB Output is correct
15 Execution timed out 15079 ms 5072 KB Time limit exceeded
16 Halted 0 ms 0 KB -